OK, I think the culprit is the "Now Listening" plugin. I tried to connect 10 times and couldn't. Disabled the plugin, restarted Kopete, can connect fine. Restarted again, connecting works fine. Enabled the plugin, restarted, can't connect. Tried a few more times, same; can't connect. Disabled the plugin again, I can connect fine.
So I think "Now Listening" breaks at least MSN. The erratic behaviour I had while connecting to MSN probably depended on whether I was listening to something (Amarok) or not.