how about a centaur barbarian/scout/monk, whatever, with horse shoes of speed. one level of barbarian and a few of scout will get you to 100ft. add half dragon and you have 100ft flying too.
Even faster than 100 ft. flight, monk levels boost fly speeds as well.
Make it a tauric human-light warhorse instead of a centaur though, that will give you a base-speed of 60 ft. Not sure how else it differs from the centaur. It has the same racial HD but one higher LA.
I'm guessing centaurs are based on heavy warhorses.
Then add shadow to increase it to 90 ft.
That's LA +5 and 4 racial HD though.
Class levels using some variants can give you:
Barbarian level 1: +10
Ranger (UA variant) level 1: +10
Ranger (CW variant) level 6: +10
Monk level 3, 6, 9, etc.: +10
Druid level 5 would give +30 for 5 minutes.
6th level Ranger is a bit useless since 3 Monk levels already give the same.
You could get 110 ft. at level 11 with 10ft. more at every 3 levels thereafter.
Actually it might be better to just get a shadow catfolk:
LA +3, no racial HD, base speed of 60 ft.
That would be 80 ft. at level 5 with 10ft. more at every 3 levels thereafter.
No the tauric one is faster after all, large though, so not as great for sneaking, but can carry a lot more since it's also quadrupedal.
Xeph's burst ability only lasts for 3*3 rounds/day max, so hardly useful for a messenger, 270 ft. (1/20th of a mile) isn't making a difference on trips measured in miles.
Even when assuming the boost is used during a sprint and with the Run feat, then it's 1/4 a mile per day in 3 sprints.
The Druid's aspect of nature ability lasts 50 rounds/day in one trip, only 10 of those can be spent running, rest possibly hustling, that's 3/4 of a mile.
This at the cost of 5 levels.
Three Monk levels (or the first level of Ranger/Barbarian) for comparison give 9 miles/day extra without the need of running or hustling or anything, so the Druid class and Xeph race are not worth it.
It might be worth to investigate if there is a race that is able to hustle all day, or walk for longer than 8 hours without penalty. This would require immunity to nonlethal damage. Maybe some intelligent undead creature?
Since they don't need to sleep and are immune to nonlethal damage it basically means they can hustle 24 hours/day increasing their daily speed by factor 6. Vampires are out of the question since they can't travel during the day. And any undead with clearly undead appearances might not be suitable for messengers.
I think this post is about long enough now, lol.