Squnk, it might help if you offer a few parameters. Are you looking for a design for a single character who is a well-known messenger in your world or a group of characters who follow a similar path? Also, is this for a player character or an NPC in a game you run? If its a PC, then it would help to know what your DM is allowing and what sort of speed you are hoping to accomplish, whether it needs to be base land speed, or whether you need to include fly, swim, burrow, and climb as well. If its an NPC, any race or class known for speed could work, depending on what you have in mind. Scout or monk are simple classes. Plenty of races have 40 base speed and a few have 50. Although ultimately if it is an NPC you don't need to worry too much about the mechanics. Your messenger can move at the speed of plot. If you intend the players to face this messenger as an opponent and you want to feel more "legit" then what sort of target speed are you hoping for in tactical combat?
Sorry, but I find your original post a bit too open-ended to think an answer would help. I could offer any one of a dozen or so race/class/magic solutions, none of which might help depending on what you had in mind.
The simplest solution to me would be an awakened animal like an eagle. Fly speed of 80 is hard to beat for an intelligent messenger. If you wanted to make it magebred (from Eberron) that adds +10 to the speed too. Add a couple magic items to the creature...
edit: I see you are looking for a "track-star" and an "NPC messenger" to "aid a villain." I think I will stick with awakened magebred eagle though.