Similar situations can come into play with Fighters and Juggernauts if the Fighters don't have the ground attack upgrade. I'm pretty sure Ironclads are capable of attacking Shamans because Shamans have been a fairly regular feature in all my naval battles and something's been killing them.
Anyway since stalemates can happen without mercenaries that can't be a fix. Also if you auto won when neither side had attacked in so long you could just give your opponent a run around. I don't know if there's a mechanic for units on both sides of an engagement surviving but that would be ideal. If you get to the edge of the map all surviving units survive. It would need coding from scratch though.
I fear realistically the only solution is going to be make sure you send a mix of troops with a range of attack abilities to every encounter on the seas.
