There should be an option where can check a box and when you add a buddy it will send them a message and then they accept it and they are both buddies. You should also add more options for buddies like shoe buddies on profile page.
This is def mod material, I've done it before.
The profile page could need some more social stuff but then again, how much and what exactly is needed calls for endless debates, thats partially why I didn't even consider adding something like this.
I dunno about shoe buddies though, thats kinda personal :P
I would recommend this two mods by dougiefresh:
It may not be exactly as you want it but it seems to serve your purpose. And you can try to ask the mod author if he can add that pm feature too.