Never used AOL so I don't have any experience with how deeply entrenched it might be in your system, but changing the IE title is easy.
I'm running Windows 2000 so I'll give instructions for the same: Start --> Run --> type: gpedit.msc --> in the window that opens, go to: User Configuration > Windows Settings > Internet Explorer Maintenance > Browser User Interface > Browser Title.
From there you can can either turn off the custom title, or change the text that comes after "Microsoft Internet Explorer provided by" to any 30-character-or-so string you want. For instance,
Microsoft Internet Explorer provided by the Fury of Professor Wolfman fits quite nicely.
And if Spybot & Ad-Aware didn't remove whatever adware you've got on your system, download HijackThis and post the log file in generates here & we can take a look at it.