Esse exemplo de Slayers é bom. O vilão pode (e deve) se surpreender com algumas soluções encontradas pelos jogadores. O problema é quando o mestre em si se surpreende, mas ele não "aceita" ser surpreendido. Daí tira uma solução malpensada na hora e justifica com regra de ouro.
E Voo é um bom exemplo porque embora muitos trabalhos de ficção mostram essa habilidade como algo excepcionalmente poderoso, é uma magia de terceiro nível em D&D. Não dá pra narrar nada de nivel 10-15 e não levar em conta que os personagens podem voar.
Eu tenho meu quinhão de NPCs que fazem coisas fora das regras. Mas geralmente eles tem um motivo pra ter estas habilidades. E se for algo excepcionalmente forte (tipo, imunidade total a qualquer tipo de dano), os jogadores já ficam cientes disto antes de sequer encontrarem o sujeito, por rumores.
Como o caso do castelo protegido de teleporte. Assim que cogitassem usar, um dos magos do rei diz que é inútil tentar porque ele tem um cristal mágico no meio da fortaleza que impede isso. Ou algo assim. Se o grupo tentar, eles aparecem no limite do teleporte, ou a magia falha. De qualquer forma, fica claro que ele não fez aquilo SÓ pra parar o grupo porque eles ousaram tentar algo não-convencional.