The problem you have now may not necessarily be the same as the one you had before - you killed the original virus.
Last week my laptop (XP) was behaving exactly as your machine. A shutdown could take several minutes.
I used Task Manager and found a process was taking up 98% of the CPU cycles even when I had no applications running. I downloaded a free utility called Process Explorer and installed it - it just confirmed what was happening but in a much prettier way.
Searches (very slow searches) on the web suggested this that and the other and I tried all the suggested fixes for an hour or two with no success.
I did a system restore and immediately all was well - the process previously consuming all the CPU is now using under 2%.
Things you might try for free are Spybot Search & Destroy and clearing out everything in the start up list - there are articles on the web that will explain how to do it - quick and easy.
Try to find out using task manager or even Process Explorer what's happening inside the machine CPU / Network / Applications / Processes - any Virus worth it's salt will not give the game away by making the machine run slowly so my guess is that your current problem is not virus related.