Well, of course it turned to be that hosting was not an issue. Someone found a hole in one of the test sites I’ve had there and sneaked in a pretty interesting script, in Chinese! I had a good laugh once I found it: chinese script injecting redirects to Russian sites, pretty darn cool, isn’t it.
So after I’ve removed all suspicious files and the script in question, everything came back to normal. Phew!
And it was a good time to tidy things up anyways, so all’s well that ends well!