But before doing what Animal suggested, test with a clean unmodified version of MSN Messenger and (most importantly) remove any plugins and/or addons you have.
(eg: Messenger Discovery "tampers" with the connection, so that might be a cause. Some plugins might interfear or at least slow down the processing and thus causing time-outs, etc...)
/ 
