Our group just had our first encounter wth a leutenant. 2 of the heroes are ranged with Landrec able to generate 5 surges automatically and dropping an average of about 12+ damage per hit. The leutenant was the siren and was placed at the far end of the ocean map and just ran away. The players called foul but after checking the rules I think that I was okay to just have her run off since I ddin't want to loose my leutanant. Has anybody else had this same kind of situation with players complaining about the leutenants being impossible to catch?

Yes many people have had this same complaint. It is entirely legal to have the LT flee on the first turn just as you did. It's especially annoying for the heroes since the LTs only flee one trail on the overland map when they flee an encounter like that. If it's any consolation to your heroes, they are entitled to the encounter loot for "winning" an encounter, so they get a little bit of gold.

Incidently, the only way I've heard of dealing with this is if the heroes have Runemaster Thorn in the party. It's possible for him to blink across the map next to the Siren and kill her on the first turn with the right equipment and skills. Without him in the party I'm not really sure what you can do to stop the OL from fleeing on the first turn. Maybe if your heroes acquired that Silver Melee weapon that grants extra spaces of knockback with surges you could punt a damage dealer close enough to do something to the Siren (maybe web her if you have a weapon that does that?). It would have to be a long punt though, and it would certainly spell certain death for the hero hit out there, though it may allow the rest of the party time to close in.

Someone proposed to houserule lieutenant encounters: in case of a lieuteant's flight, the heroes would get a partial reward for the encounter. That is, 2 conquest and 125 gold. I think that's a pretty good way to balance things out a bit.

Thanks for the feedback. Good to know that we're playing it right and that others had the same problem.