my guess....if problems presist after removing the malware then it has some thing to do with Registry entries...provided there are no other active malware...
Correct. The malware may have deleted the SafeBoot registry keys.
Here are some options to restore them:
http://didierstevens.wordpress.com/2006/06/26/restoring-safeboot/
http://didierstevens.wordpress.com/2007/02/19/restoring-safe-mode-with-a-reg-file/