What is your site's URL? The reason I ask is because I just tried sending a message to someone not in my friends list on my own site and it worked fine. It would be better if we could see what errors you are getting first hand.