Hm.. perhaps, in the case of messengers, how 'bout this? Buy a caged raven, give it a conversation that lets you open the inventory, place your letter or whatever you wish to send, so long as it's within weight limits, then speak the character's name to the raven, at which point it'll do the 'fly' animation, and teleport to the character in question (with a delay, no doubt).