It could be that this is complete rubbish now, but: Doesn't Jabber (the IM-protocol supported by the Nokia ITs) handle MSN and ICQ via so-called "transports" on the server side? I never tried it and don't know if the client (=N800 in this case) needs to meet any prerequisites, but it could well be that all you have to do is register your existing MSN/ICQ-IDs with the respective transports on your Jabber-server and you'll get all of your Instant Messaging handled via the built-in Jabber client.
There's also Gaim, a multi-protocol client, that should support those protocols; the download page says nothing about N800/ITOS2007, so it could be Gaim works with the 770 only.
Yes, Gaim works fine on N800. And yes, you can use the original N800 jabber client to connect to msn. You need a jabber server that provides a gateway to msn network. I think you can find more info from this forum or from jabber homepage.
i get my Wifi at home, this week hopefully .. somehow i can't update the repository list when i'm connected to my N73 (GPRS/3G) .. and Wifi Hotspots are very rare here in austria .. and don't think about free ones, there are none ..