It doesn’t sound like you’re having the exact same issues as me, but I thought I’d add my issue/solution in case it helps.
It looks like my host was hacked and some malicious code was added to my .htaccess file.
It looked like this: https://gist.github.com/737848
It sounds like your issues are more pronounced, but might be worth it to just check.
This is hosted on Media Temple.
This is the same issue that I’m having.
