So I think I figured it out. My sync works up until the moment, where I merge my contacts with my IM-contacts. I tried it with msn-haze and msn-pecan, same result. The sync takes a couple seconds to finish, every time I sync. Once I merged, the sync takes forever and then times out with the well known "check your server details" etc etc.

So merging contacts seems to be the culprit. Respectively merging contacts seems to trigger something harmful to the sync process. Once you do a full resync and do not merge, the sync will continue at least it did for the last couple hours for me.