As much as I feel flying mounts make the world feel smaller, I still don't want them gone. And if you put fatigue on a flying mount, it would just end up being annoying IMO.
"Come on... I only need to get over one...more...mountain range! NNNNOooooooooo..." *Gets stuck in a crude pit in a cross-zone mountain range*