are you sure ALL* has been deleted ?.as far as i know theres a virus which causes this !!!..i forgot the name but make sure you have a virus checker for the registry also, trojans,worms and so on.
If you are very sure theres no more viruses then i suggest you repair you OS installation.