This... ...is actually pretty workable. All it needs is a separate second world map, let's call it "cloud map", and we'll be away laughing.
Or if we wanted just one dungeon to be found in the clouds, we could add something like a random chance that instead of this message
, game::TryTravel() to that cloud dungeon will be called. Though exiting that dungeon would then need to be special cased, if you were able to enter it from any location on worldmap, otherwise the game might get confused where to put you on the worldmap once you get out.