hmm,
bei Leadership ist der DM nicht auf besondere Wesen oder Tiere wie beim Familiar oder Animal Companion beschränkt. Von daher kann man auch einen Menschen zur Verfügung stellen. Für den Zweck sollte es dann ein Mensch sein, der Overland Flight, Teleport, Transport via Plants, Treestride, Phantom Steed, Planar Ally oder Sending beherrscht.
Oder Wildshape, der dann wirklich als Brieftaube hin- und her fliegt.
Ein Troll hat je nach Kampagne doch Probleme am Zielort die Nachricht anzubringen.