A simple fix would be to dissallow non-naval mercenaries on such maps?
That's no fun. Shamans are a nasty thing to have to deal with when they're upgraded, it adds some interesting flavour to naval matches.
Besides, as Rack pointed out, Imp Fighters with no bombs versus Juggernauts is also a stalemate, mercenaries or no.
