Why wouldn't Blizz do a flying mount for locks?
The model would be a red bat without fur on it, like a sort of fel bat. Epic version would also have fire coming out of his eyes, mouth, and would have a fiery mane.
Normal version would be quest obtaineable, you'd have to kill the elite wild version of the bat somewhere in Hellfire Peninsula. But you'd still have to pay for the training.
Epic version quest would be something like the druid epic flight form quest, you go all around Outlands battling diverse demons in order to gather the reagents and summon the epic felbat into the world. final step would take you into, say, Shadow Labs, where, after defeating Murmur you use the instruments of the shadow council and your own reagents to bring the felbat into this dimension and bind it's spirit to you by vanquishing it. Once again, just like for the druid's flight form, you'd have to pay for the training.
Another possibility would be: you don't have to pay for the training. But since you're bringing an forbidden entity into the world, that could have destroyed Outlands, the quest would decrease your reputation with certain factions.