The Tavern

Any other option than random teleport?

Blink or dig or fly?

You can try burning the trees, but you might well have to give up on this rune. There's usually stone behind the trees. In this situation I'd probably decide to get Abyss / Slime after your 2nd rune.

How frequent is such a thing? Is it possible to lock yourself out of Zot this way?

I would report this as a bug.

The easiest fix is the Corruption does not place undiggable walls anywhere.

Go for 15 runes for experience and cast Shatter.

Shatter, switch to Fedhas, or perhaps most practically if you didn't kill everything inside the vault you can wear a *tele item on purpose and just wait on the floor to get in, using tele to get back out.