Search Engine Redirect Hijack

I administer the website http://www.skeelesinc.com and the last few days we have been dealing with a redirection hijack that only seems to happen from search engines. Almost daily the site that it tries to redirect too changes, it seems that it is always a .ru domain, and it never resolves. I have been trying to figure this out all day, with no luck.

First thing I did was update to the latest version of WordPress as ours was a few months out of date. I then updated all the plugins. When that didn’t help I disabled all plugins. After some googling I found that most of the results for this problem were from 2008, but I followed them anyway. I manually checked the primary .php files for any suspicious code. I checked around for any suspicious images. I checked the database for odd entries, and removed any that I found.

I am sure that there are a few other things that I have tried, but am too frazzled to think of right now. Anyone have any suggestions on what my next move should be?