Well, in order to totally remove AOL without reformatting, you'll have to replace the winsocks as well!

As AOL also modifies them.

And as RicheemxX said, " You'll have to edit a million reg keys to get rid of it as well."
I've found it possible to remove most, but not all traces by running the uninstall from Add/Remove Programs, deleting any AOL folders, then running
JV16 Power Tools (Reg Cleaner) to clean up the Registry. Finally, I replace the winsocks, remove the modem from the Device Manager and install different drivers for it. (AOL tends to modify the modem drivers as well.
So, as said earlier, the easiest way to completely remove all traces of AOL is by reformatting your HDD.
Harder