I'm neutral on whether the mercenary card should stay or go, but to respond to your two points:
pubby wrote:1. Mercenaries die easily due to bad AI and AoE effects
I don't see a problem with this, as long as it isn't avoidable in some silly way. Most cards are not meant to be game-changing effects, especially at low powers.
Your solution would also be a massive noob trap: it's not worth it to repeatedly pay pretty much any amount of gold to continually revive a merfolk or a naga. Even the deep elf blademaster wouldn't really be worth it (especially if you'd have to pay 2000+ gold each time it croaks). Basically, characters who could actually spare the gold to do this would have absolutely no need to do it.
pubby wrote:2. Mercenaries become separated and lost when you travel to different floors without them
I agree that this needs a solution. It's minor in this case, but it's pretty much a pure interface annoyance, trying to shepherd permanent allies around. Personally I think Brogue-like interlevel following would be better than a Recall ability, but the ability has the advantage of not requiring any new coding, and therefore being more likely to make it in.