i love listening to people that loves to preach... people that have no idea about how search engines nor simple webmaster things actually work...
1. tell your host. They need to remove the infected machine from service and replace it with one that hasn't been compromised and is up to date with security fixes.
2. examine any server side scripts you have to security vulnerabilities If you are using third party scripts - make sure you are using the most recent version and that there are no reported vulnerabilities. In case your scripts are not infected, it's probably DNS poisoning or DNS hack.
3. Use the google webmaster tools. You can notify them to rescan pages.
oh, and i forgot to tell ya: you don't have to rescan your pc, because YOU ARE NOT INFECTED!
