I currently have deliberate redirects set-up and running, other than some handled by the W3 Total Cache plugin… oh and I redirect all of my 404 errors using:
ErrorDocument 404 /index.php?error=404
in my root .htaccess.
Try installing W3 Total Cache, see what happens? (I have run out of real ideas now!)