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.