most of the tools AOL provides suck. sounds like you have some hidden script or something that is automatically resintalling the spyware, if AOL even removed it in the first place - the really persistent stuff is very hard to get rid of.
Do you have service pack 2 installed? have you got MS's antispyware protection installed? have you tried Lavasofts Adaware?