Here's some crazy ideas. Not sure about the difficulty to implement some of these. Also, I'm trying to create multiple ways of accessing the same cards/items (ie you can pay a lot at the Auction House or the right shop to get a card/item or you can do a bunch of smaller things, go to one of these special buildings and get that same card).
Astral Plane: Sacrifice X immortal creatures (or instead maybe X Dragons from Y elements) for a Quintessence Scroll (cannot attack or be attacked for X turns).
Laputa: Pay 2 Wings and a weapon to receive a Flying Weapon card or 2 Wings and a creature to receive a Dragon from the same element of that creature.
Vodouisant Shrine: Sacrifice X cards to destroy X/2 of the same cards from enemy player. Or if that's too OP, sacrifice X cards to ban the same card from being used in targeted player's next fight. Targeted player cannot have this done to him on consecutive turns.
Crypta Letum: Sacrifice X creatures to receive a rare card (not sure if it should be random or chosen).
Milthril Cavern/Mine: Pay X amount to upgrade any permanent.
Al-Khemi: Alchemy shop to mix and match spells to create other spells (ie bring 4 different CC cards to create a Pandemonium spell)
Vulcan Forge or Vulcanis: Morph weapons into other weapons (ie bring 2 Dirks, 1 short sword, and 2 Long Swords to create an Arsenic).
Meka: Pay X amount to upgrade any spell.
Sacred Grove: Transmogrify creatures into other creatures (ie bring 3 cockatrices to create an Emerald Dragon; bring 1 creature from 4 elements to create a Chimera).
Sanctum Luxim: You cannot be attacked in this place. Sacrifice a dragon to nullify any quest to kill you (or instead maybe to force peace between you and another player for X turns).
Machinus Tempus: Pay X electrum to save your progress. You could make this increase in cost each time or set a cap on the number of times you can do it.
Nautilus: Transform X cards to X/2 corresponding cards of another element.
Arcus Iris: Pay X electrum to upgrade any creature.