Net Messenger in XP

It all depends on if you're using a firewall, NAT router, or anything of the sort. I have found that firewalls and Messenger really disagree with each other. To my understanding, this is how the process works for Messenger:

After you click the 'Enable Voice' button, your computer thries to connect to the other computer (Either directly or indirectly, I haven't checked this out in a great amount of detail). When a connection is established, then the other end then procedes to try to connect to you, at which time your firewall spits back (Or ignores them, depending on how your firewall/NAT is set up.). Either a timeout waiting for the connection to come back, or a message passed along the data stream occurs, and then it realizes you can't connect.

I don't have thewm handy. However, if you look in the Messenger help on the web-site, it will tell you what ports to configure on your router to allow pass-through to in behind the wall. Check it out.