Recently, Windows Explorer has been a major problem in my Windows Vista operating system. It would often display error messages such as Windows Explorer is not responding and asks to close or restart, at first I thought it wasn't that big of an issue.

Although recently EVERYTIME I boot up my computer the taskbar would completely freeze, and everything would be unclickable. The desktop still works fine though, until I open up Windows Explorer it loads very slow and when I try to right click > create new file the menu freezes as well.

The only way I could correct the frozen taskbar would be to ctrl+alt+delete and stop/start Explorer. Even then it would still have a chance of freezing again on me. I have tried many spyware/adware/virus scans (norton, spybot, adaware, avast, nod32), and in safe mode I still can't create new files using right click.

I highly suspect that my Explorer is infected with a virus but I don't know how to fix it, any suggestions would be very much appreciated.

Thanks in advance.

assuming you have already tried steps here
http://wiki.castlecops.com/Malware_Removal_and_Prevention:_Overview

did you review errors in eventviewer logs?

Cudni