This is an on-running problem with MS Messenger with many of us experiencing the same difficulty. A search of this site will reveal various suggestions, but no real answer. The variant of Windows does not seem to make a difference. You could both try shutting down any firewalls you have to see it that helps.
You could also try Yahoo Messenger or Eyeball chat. Personally, I use Yahoo Messenger.