I suspect redcaps can get away with more than other mages- after all they don't have arts which require one on one training, and they are pretty much forced to interact with mundanes in order to deliver the mail...
Redcaps need a lot of Lore and quite a few General Abilities
A Redcap needs:
Area Lore, possibly several
Faerie Lore
Organization Lore: Order of Hermes
Code of Hermes
Infernal Lore
Magic Lore
possibly Civil/Canon Law or Common Law
Athletics
Awareness
Bargain
Brawl
Charm
Etiquette
Folk Ken
Guile
Intrigue
Dead Language: Latin
Profession: Scribe
Stealth
Survival
Plus a couple of other languages, depending on where they are traveling. Artes Liberales is a good idea, since they deal with the educated. Probably Single Weapon, for self defense on the lonely road. Possibly Thrown Weapon. Possibly some other sideline abilities to give cover, like Music or Legerdemain. Some Redcaps have Magic Theory, although I suspect this is a knowledge gained later in life.
If they have supernatural virtues, they also need to have the related skills.
All of this soaks up a lot of experience points, although many of these skills don't have to be high to start. Redcaps are not just messengers. They are spies, traders, scribes, and the general apparatus of the Order.