As far as I can tell, you can never "beat" a palace, i.e., turning it to stone.
As for the key for the lady locked out, that took ages for me to find.
I found a lady who wouldn't talk to me unless I had 7 magic containers, but after getting the cross from one of the palaces, she let me in, even though I only have five. So, I'm able to progress to the great palace, but assuming it is like the original game, I'll need Thunder magic there, which I've not found, so I hesitate to explore inside. And I still only have
6 magic containers and
7 heart containers... Not really sure where the others are hiding, and I'm not sure I'm up for another check every square of the world map search, as I've pretty much done that already when looking for other things... There's always checking every tree and rock wall with the hammer, but...