AOL will un-install pretty much everything from Add/remove programs, and to all intent will give you as clean a machine as the removal of any other ISP. Yes there will still be some lines in the registry, but none that will affect the running of your PC.
It may be a virus, need more information. Do you see a message on-screen prior to shutdown, if so what does it say? J.