My SO and I have used ICQ to communicate with each other for nearly 10 years (my original ICQ number had only 7 digits in it; new numbers have 9 digits in them). ICQ is still my SO's preferred instant messenger, primarily because it allows users to send messages to contacts even when those contacts are not online (the messages are stored on a central server, and then delivered when the contact comes online).
However, when my SO attempted to start ICQ a few weeks ago, a message popped up giving my SO the choice between closing the program and upgrading it. Upon clicking "close," ICQ did just that. In fact, it completely refused to run without being upgraded. This is not a way to keep your customers happy (especially when your customers don't have administrator access to their work computer and thus can't upgrade their software).
This forced upgrade, combined with the ever-present ads, motivated my SO to finally switch to an alternative: Gaim. Gaim is an open-source instant messaging client that connects with most major IM networks (MSN, AOL, ICQ, Yahoo, Jabber, and Google). It is completely free, has no ads, and neatly integrates all of your IM accounts into one single interface. It comes installed by default on Ubuntu (where I'm happily using it as I type).
Unfortunately, promptly after switching to Gaim, my SO started getting spam ICQ messages. Based on some quick searching it seemed like this was a long-known bug in Gaim (the privacy settings seem to have problems in the Windows version), and thus my SO gave up on Gaim for Windows. My SO went back to ICQ (and upgraded), but if I get back to using Windows at home I'll probably try Trillian, another free instant messaging client.
So, if you're looking for an alternative to ad-filled, proprietary IM clients, go take a look at Gaim or Trillian; they may not be perfect, but they'll be ad-free and will completely lack forced upgrades.