I haven't changed hosting providers yet. I have GoDaddy. I put out a call for help, and I want to wait and see what the experts say first.
I've tried AntiVirus (which found the latest problem before I did), Hide Login, and Secure WordPress. Those three are on my blog that supposedly hasn't been hacked yet, so I'm pretty sure they're safe. But I don't trust anything anymore! lol
You might want to check out some of these plugin recommendations. I don't know how effective they all are and not all of them are tested with 3.3.1. But they're worth looking into.
They *might* help you figure out where the problem is coming from, depending on your issue.
One of them had detected a problem with my index.php in Twenty Eleven as well, along with a bunch of other things. But I don't think it's related to the theme itself.
If you get redirect malware, try this. It checks the files in your theme.
I think there was another good plugin, but I can't remember it atm...
I would also delete any themes and plugins you aren't using. Don't just deactivate them, but delete them.
Try also checking your site via Sucuri. It will tell you the pages that are producing problems (but that doesn't mean that's where the problems are).
This whole thing has been a huge wake-up call for me. I just wish I could fix it. lol