Hi,
What you need to confirm is that the messenger contact request email to the outside user isn't being blocked by your spam filter. As an example of the email being sent from your device to the requested contact I have posted a sample request from my handset below:
----------
Gary Cutri would like to add you to his or her BlackBerry Messenger Contact List.
If you don't currently have the required application on your device, please visit
www.BlackBerry.com/messenger to learn more about this service.
Once you've installed BlackBerry Messenger, return to this message to accept this request.
-------o-------
80:AQEBAAEBBAACCCmpcgAACAEAAwAVAAQCmyvEtzzV2hX1mSp e8BAg/RxuLsBAAUuAQAGLgEABA=