Just like the title says. I casts the spell on the sk city and walked right in without the keys.
I cleared almost the entire map and never saw the ice lieutenant. But that doesn't matter, as the keys were not needed.
Let me know if you want to see the save game.