I have this exact same issue and it was NOT resolved by using Adium, the only difference is that Adium automatically signs me back in without me noticing, so i am often unaware of the issue.
However, I have found most of my messages are not received by my contacts and vice versa, making communication nearly impossible.
File transfers are also hit and miss.
I believe this problem is something to do with my modem, but no one can seem to tell me how. The reason I say this is that the problem started the very day I installed broadband. MSN previously worked fine using my Mac's internal 56k modem, it also worked fine when I was on someone else's broadband connection, I have disbabled my firewall and after 2 different versions of MSN Messenger and Aduim, the problem is still unresolved. I can only see that it is my modem settings.