I like this idea, and I have some suggestions on it.
1) I think that every large town should have a post office nearby, for deliveries.
And 2) I think that everyone should be a postman, say someone is travelling from up north to Clayshire or Laketown, they can drop any letters they have off there, and if one of them is to someone in Bottleneck, it would be picked up by someone who is travelling that far and left at that post office.