I have a quick question for you. I have been working back and forth with my hosting company to make a few performance tweaks. Here's what happened over the weekend I was running PHP 5.2.17 with your wp-cache-phase2.php fix/update and had no issues with the original problem.
We have now updated to PHP 5.3.8 and they noticed that we had a large number Crons running, which was causing the site to bog down. So they installed WP-Cron Control plugin. Now I am the having the very random page redirect again when WP Super Cache is enabled.
This is what is happening if you go to page 3 first, then go to page 2 you will see the "Search Result" in there.
I'm working on getting a De-bug report.