Dude, you’re so not paranoid. This stuff has happened to me. I had a Wordpress blog that was hacked and the exploit was stored in the DB so even after reloading the OS I still was infected because I hadn’t sanitized my database. Luckily it was just Google search viagra spam, and it was a valuable lesson.