I've been having this problem for the past two weeks now, and it has me stomped. My MSN contacts reported to me that all of their messages failed to be delivered to me as soon as they hit send. It's fine once I initiate chat with or respond to the contact, but there appears to be some sort of timeout where after an unknown number of minutes, it'll revert back to failed messages from contact. Again, I started having this problem about two weeks ago, but I didn't change anything related to Adium that I'm aware of. It worked fine in the same network environment for two years before. I'm using Adium 1.4.3 on OS X 10.6.
I'm actually not sure if this is Adium's problem, as I've been able to recreate the issue using Microsoft's Messenger client for Mac. Interestingly, it seems to only happen with this particular MSN account (it's an MSN Passport account, not Hotmail or MSN.com).
If you guys can point me in the right direction, that'll be greatly appreciated.