MSN Messenger - When Connecting Internet Connection Dies

I have had this problem for a long time but I've always either avoided it by
not using MSN Messenger (this occured for both version 7.0 and 7.5).

When I first sign in my Internet connection would die and MSN Messenger
itself would not respond. It would wait for at least 20+ seconds before
saying it cannot connect. Then I would sign in again and again connection
would die then sign in after a small wait (~5 seconds). This is the usual
case - the first being a failure and the second time being successful,
however there have been time where the 2nd time also refused to sign in. I'm
not entirely sure what the problem is because I have removed Windows
Messenger and I have re-installed MSN Messenger (several times, either repair
or un-installing). I have removed Windows Messenger because one of my
friends have said that was the cause of the problem but the problem still
exists (before and after Windows Messenger)

I'm using Windows XP SP1 Pro. with cable. I am using AppLocale and I have
heard that it may mess up installation (regarding Windows Installer 3.1) and
I have foobar2000 as my audio player with Toaster to display what I'm
listening to. I used a similar program for WinAmp. I think that covers all
the possible related problem. Please let me know if I need to provide any
more information.