Reading the other topic, called Noble Houses, I got an idea.
What if, when you're in a certain region, you could visit the local estates?
There would be a link under Actions, "Visit local estates" (like there's Visit the Temples", etc.). This would bring you to a drop-down menu of people based in the region. Visiting the home would have no consequences on the level of game mechanics. You would simply get a special messaging screen (similar to the message field you get when transferring funds?) (also adding the person to your contact list? -interesting for diplomats).
Messaging someone using this channel would basically let the person know you're asking them to roleplay with you. This could be the visit itself, or another activity. Basically, it would be the medieval equivalent of poking someone on facebook
it would also flesh out first encounters, as the receiving persons can easily present themselves.