I think its server lag tbh. This happend to me flying from STV too Wetlands. As i was coming into SW the bird dropped me right into a n00b group and killed me. They were wtf just happend. Warlock just fell out the sky in front of us and died.
When i ran up to the gates of stormwind after there was a bunch of people all stuck by the Elwynn Forest/Stormwind zone in and they were unable to enter stormwind with the same instance error.
Been playing since launch across 3 different characters, only encountered a single bug so far. In Retail you can barely play the game for the first 2 weeks after a major patch due to bugs making it impossible to proceed.
This bug is as old as the game itself. Lag, lost connexion for even a split second, or flying over a dungeon at the right moment, or a zillon other thing can cause it. I have been killed by this … not a lot, but frequently … from one of the first times I had enough G to pay for a Gryphon ride back in Vanilla. The Instance not found - message is a Classic!