I had an issue where a compromised plugin on Wordpress allowed a user to get access to insert a malicious script that is causing an intermittent redirect to an inappropriate site. I've deleted every filesystem folder, and re-uploaded files from a brand new download after going through each one looking for anything malicious, and the files are all clean. There are no .htaccess files that are compromised, the databases don't appear to having anything malicious, etc. Is there any other place else on the server I should be looking higher up above the filesystem? Could there be anything in the /conf folders, etc.? This redirect has been almost exclusively affecting mobile devices and macs - so I haven't been able to recreate it.
Is it possible they were able to edit the DNS, or maybe its a browser cache issue and you just need to clear your browsers cache?
Any direct access should be coming from the web server level. Theoretically, if a hacker has access to your account they could create a cron job and run a script from locations above the publicly accessible web root folder. In your database, just look for iframes and any rogue javascript. Other than that, I think you've done what you should.
Here's what you do - you wipe EVERYTHING - database, files,everything. Then you reinstall and reupload only things you know are safe. That's the only way to be sure (and even this will only take care of anything inside the web-folder - if anything is running with hightened access outside the root of the webfolder, then you're in a bit of a mess).
Before doing an OS reload you'll need to check the logs to understand the issues you're facing. You can reload the server but if you don't know the cause of the issue then changes are that you'll have issues again as whoever had access to your sites/server will try to do that again.
Granted, I didn't suggest an OS reload - just a web-reload - ie, software running on the webserver, databases etc. I wasn't suggesting a complete OS-recovery, although that is of course the only way to be completely sure that everything is wiped.