Basically:
Mailboxes could be bound to hearthlings. So that you could own a mailbox or mailboxes.
Then there would be birds, pigeons or such, that you could use to send messages to mailboxes of people on your kinlist (if they have a mailbox)
Pigeon would fly, kind of like a nidbane, to their mailbox, drop the message off, and then fly back.
Pigeons would of course take some file to fly into their destination, and slight chance of them being lost or killed (by an eagle or something) in the way.
Amount of pigeons could be also limited, to prevent people from sending like 1000 pigeons (like in the harry potter movie/book)