Update for ICQ 2001B/2002
See this site, which has up-to-date info on removing ICQ ads.

ICQ version 2000b has apparently added advertising windows -- we knew the AOL involvement would only screw things up, right folks? Anyway, these eyesores are downloaded from ads.web.aol.com (among other places) in the fasion of AOL Instant Messenger. Oscar writes in a quick and dirty solution to block these ads:
Find the ICQ web cache directories (usually C:\Program Files\ICQ\AteBrowser\#########\cache\ where ######### is your ICQ number) and replace each "cache" directory with a read-only file by the same name.
(Note: This is essentially the opposite of the "Replace cookies.txt file with read-only directory" hack for old versions of Navigator.)

Another solution (for the SMS banner at the top of the window) comes from GRC's newsgroups:
Close ICQ, then Program Files/ICQ/Partners then open the partner.xml file, clear all the text from it, save and close. Mark as read only too.

To turn off AutoUpdate (to keep them from 'upgrading' the software without permission)
Go into your registry and look for auto update. It's most likely in:
HKEY_CURRENT_USER\Software\Mirabilis\ICQ\DefaultPrefs
And set the value to "No"
Note: this may or may not be beneficial. See below.

If you don't use new features in the new AOLified versions of ICQ, you can probably use an older, pre-AOL version, which does not have spamvertising windows. (I currently use version Beta 1.113, dating back to 1996, which works just fine! Doesn't eat MB's of disk space either :)
You can find some older versions (maybe not THAT old) at this site.

If the new ICQ is versatile/foolish enough to let you use it through a proxy server, set up the ad-filtering proxy of your choice (Proxomitron, AdSubtract, Junkbuster, etc.) to block the adserver, and set up ICQ to connect thru this proxy. Or for now, add the following lines to Windows' Hosts file (C:\Windows\Hosts):

127.0.0.1 ads.icq.com
127.0.0.1 cb.icq.com
127.0.0.1 cf.icq.com

A hack posted below lets you strip ad-spaces right from the DLLs and regain precious desktop real-estate. For those lacking the experience/ambition to undertake it themselves, yeh.tech has a package called ICQ Strip which incorporates the updates.
 

Jason shares the following advice snagged from the newsgroup alt.icq:

STEPS FOR ELIMINATING BANNER BOXES ON ICQ

Make sure ICQ is not Running.

1- Download Reshack from
http://www.users.on.net/johnson/resourcehacker/

2- Look for Auto Update in your registry
HKEY_CURRENT_USER\Software\Mirabilis\ICQ\DefaultPrefs
And set the value to "No"
I've heard a number of reports that indicate the software was somehow updated (to show banners) even on systems with AutoUpdate turned off. Best to back-up your ICQ files after performing any hacks, in case AOL tries to change them on you.

3- Delete the following files from your ICQ folder
icqateima32.dll (removes advertisement downloading)
icqateimg32.dll (removes the loading of images)
icqateres.dll (removes part of the advertisement function)

4- Open ICQCore.dll in Reshack. ( this is where it gets interesting)

4a Go through each of the Dialogs till you see one with a banner box.

4b Click the banner box and it will highlight the control for that box.

4c Change the last 2 numbers in that control to 0, 0
Example:
   CONTROL "", 1070, "{9F9012BA-E55B-11D3-ADE7-0090270D8F00}",
0x50000000, 1, 158, 260, 38
Becomes
   CONTROL "", 1070, "{9F9012BA-E55B-11D3-ADE7-0090270D8F00}",
0x50000000, 1, 158, 0, 0

4d Change the main dialog box size coordinates (at the top of the
script) to Ad box y coordinate +1. Example: for above control you take the 158
   then change the main dialog box y coordinate to 158+1 (159) So;
   2503 DIALOGEX 0, 0, 262, 196
Becomes
   2503 DIALOGEX 0, 0, 262, 159

   NOTE The last four digits are position/size coordinates - first set
is x,y position, the  second set is x,y size.

4e Compile the script

4f Repete for all dialogs with banner ads then save the file (Have a
backup of ICQCore.dll just in case something goes wrong)

Henrik reports an additional change that makes the whole hack look better: to remove that line that is left just edit the last number on the last line to 0.
 

   CONTROL "", 1069, STATIC, SS_BLACKFRAME | SS_SUNKEN | WS_CHILD | WS_GROUP, 0, 157, 261, 1

Becomes:
    CONTROL "", 1069, STATIC, SS_BLACKFRAME | SS_SUNKEN | WS_CHILD | WS_GROUP, 0, 157, 261, 0

Douglas writes in to add that there are additional .dlls to modify to remove ALL annoying banners. They are:

ICQWP.dll
ICQSearc.dll   (this is where the classic mode search is located, as opposed to the wizard)
ICQSMS.dll
ICQVoice.dll

You can eliminate all HTML (ad) rendering by zapping (move/rename/delete) icqhttp.dll . Note that this doesn't affect the banner windows themselves--use the above for that.

Note: see the General Neutering section.

More links
ADBusters' ICQ ad-removal site - Includes the ICQ PowerCrack that does the following:

• Gets rid of the Ads and Banners in ICQ 2000b by replacing the Ad
• Infested DLL's in your ICQ folder.
• Changes "AutoUpdate" to "NO"
• Gets rid of the "SMS" Ads by replacing the "Partner.xml" file.
• Gets rid of ICQ Phone ads. (4.65 only)
• Allows you to add contacts without authorization "AutoAuthorize"
• Shows IP Addresses of all your contacts in info (icq99 style)
• Stops ICQ from adding "From ICQ" to IE favorites (4.65 only)

"All trademarks are hereby acknowledged as the property of their respective owners." So don't even THINK about suing me :)