Does the Paladin count as an adventurer for the purposes of the Magic Key spell?
Good question! From the FAQ: What rules and cards affect the paladin in combat?


  The paladin is still an adventurer, so
  anything that affects adventurers
  affects him (including traps and
  attacks that damage all adventurers).


So in your example, you lose your Paladin. Dungeon Lords is indeed a brutal game...