It's probably not malware......
I would do the following:
create a new 2003+ type (Unicode) PST file
don't "import" your old pst into your new one from within outlook......
copy (drag-and-drop) all data from your backup file into the new one
copy (drag-and-drop) all new messages from the previous PST file
Edit: Sorry, I didn't pay close enough attention....now you're saying this is happening outside of outlook as well?
Edited by wiczjr, 30 June 2011 - 03:29 PM.
Both faith and fear may sail into your harbour, but only allow faith to drop anchor.