My favourite messaging software is WebMessenger from www.webmessenger.com
.... It is very reliable whenever the network is running properly and the BES server is running properly.
Other people may prefer to look at BlackChat (free ICQ) and IM+ (cheaper MSN/ICQ/AIM), as they both work on BlackBerry. There's 2 other clients that work on the BlackBerry nowadays, but they slip my mind at the moment!
For desktop use, I use Trillian which puts MSN/ICQ/AIM in one contact list (one buddy list), and you can put an ICQ skin or MSN skin theme so that your MSN/AIM/ICQ look like one of your favourite clients. Trillian is at http://www.trillian.cc