Use Jabber!

Jabber is an free (as in free speech) instant messaging technology, like ICQ or MSN - It uses XMPP (an XML like protocol) which is highly extensible. Anybody can join the Jabber network and set up own jabber servers which are able to connect to any other jabber server. The whole Jabber infrastructure slightly equals the email (SMTP) system which can also be joined by everyone.
There is no central server which handles the whole communication of all members! If you have your own Jabber server (there are many OpenSource Jabber servers available) there is nobody who can unauthorized read your messages or claim any copyright (see http://en.wikipedia.org/wiki/ICQ#Criticism) on them.

I run my own Jabber server (ejabberd, http://en.wikipedia.org/wiki/Ejabberd) and it does not produce any notable CPU or memory load. It connects perfectly to the servers of my contacts - The setup took about 1 hour and i have not had any problems so far.

Check out http://en.wikipedia.org/wiki/List_of_Jabber_server_software for a list of Jabber servers.
As you can see there are a lot of servers available. Many of them will be in the repository of your favorite Linux distribution (though there a jabber servers for many more operation systems) - Check them out. I prefer ejabberd. It has an easy to use web interface.

Of course there are a lot of public Jabber servers if you don't want to run you own one. Ask Google or use the probably biggest one: http://jabber.org/ - The registration process may be unfamiliar to you: You don't have to sign up on the website. As on many public Jabber servers you can just point your Jabber client to jabber.org and register directly with your client. You will then immediately have your own e.g. @jabber.org or @example.com address. Friends can now add you with this address. Every Jabber client should be able to register you to public Jabber servers!

See http://en.wikipedia.org/wiki/List_of_Jabber_client_software for a list of Jabber clients. I use Gajim (not Gaim) on Ubuntu. It is easy to use, fast and supports PGP/GPG for client to client encryption of your messages. (Which is also a key feature of Jabber. Server to server encryption is also possible)

All in all Jabber is a great alternative to ICQ or MSN. There are so many extensions to the XMPP protocol that make Jabber unbelievable versatile. Check out http://www.xmpp.org/extensions/ for more information.

Check out http://chaosradio.ccc.de/23c3_m4v_1667.html if you speak German and want to know more about the versatility XMPP and Jabber.

Use Jabber!