What I know is that it doesn't work in the live server I'm from, EU-Kael'thas (FR), but not because I can't use the broom in an unknown zone -- the error I get is "can't use that while moving", regardless of me being jumping around in Durotar or falling to death behind the blue wall.
EDIT : but as I said I could do it this morning on EU-Brill (PTR).
I think the answer could be this : when you go directly north-west you leave Teldrassil. But when you go north then west you don't, thus allowing you to do the broom-trick.
Behold now my amazing MS Paint skills, and stand still before their magnificence -->
This would explain the fact that some people can use the broom behind the walls while other can't. And, keep in mind, there are servers like mine where you just can't use the broom while moving (although it's instant).
But it's just an idea, maybe not the truth. Requires some testing.