I experimented successfully with this recently, laptop to laptop, using a standard dial up connection at both ends.
Although I had no connection problems I can think of a myriad of potential reasons lurking in individual computers that would cause such. Additionally, I believe that some have encountered specific problems when operating in the wirefree enviroment. One bit of basic preventative troubleshooting - and the only one I took - is to ensue you go through the Messenger "Audio Tuning Wizard", to be found under the "Tools" tab. Certainly with a laptop (and probably relevant in all cases), although speakers and mic. are provided, seperate headphones and mic. are essential to avoid feedback.
I was quite surprised by the quality of the conversation. Difficult to describe; but as if the other person is in the same room with you, but completely different from the sensation you get from a standard land based telephone conversation. Likewise mobile, to answer your question.
Great potential long distance/overseas.