As a second step I downloaded Messenger:Mac. I installed it and it worked...but again, just for the 1st time. On the next boot I wanted to open it and again...error message.
Sign in to Microsoft Messenger failed because the service is not available or you may not be connected to the Internet.Not very helpful, since the service was available (webmessenger worked) and I was definitely connected to the Internet.
Now I finally found the solution. You need to check the option "Connect via HTTP" in the MSN account preferences in Adium. Then it works. It seems as if it gets blocked otherwise (I switched off the firewall without success).