Magento – Site randomly redirecting to localhost

I've to a Magento 1.9.0.1 site running that's started randomly 302 redirecting users to localhost. The site's been running for about 2.5 years now and this issue just started happening yesterday. The symptoms I've seen so far are

• a web page will randomly redirect to localhost
• admin pages work mostly fine with the occasional redirect, but this happens much less frequently than the frontend
• it comes and goes. sometimes all that'll happen is I'll get redirected and then sometimes it won't occur for long periods of time
• when a page would load, links would get populated with localhost (i.e. localhost/myaccount or localhost/someCategory

Here's the things I've checked so far

• make sure secure and unsecure base urls are correctly set – they are
• flush cache and reindex everything to see if a bad setting got stored somewhere – didn't help
• check .htaccess for redirects – none present other than ones that have been live for a year or more
• check Apache config for redirects/rewrites – none present
• point to each app server individually to see if the problem was localized to a single server – it occurred on both app servers

The other odd thing is that when the issue first started yesterday, it was extremely intermittent. But then the problem got worse until everything on the site, except the admin section, was redirecting to localhost. However, towards the end of the day, the problem seemed to go away. Now today, it's back to being extremely intermittent, although it doesn't seem to be getting worse…thankfully.

I was tempted to say it was something in the database, a SEO setting or a redirect setting in magento because I could go into index.php and set it to echo hello world and then exit and never once got redirected. It wasn't until Mage::run was called that the redirect occurred. To test that though, I made a copy of my database that I could point my local build to with the idea of stepping through things in the debugger to find where the redirect was coming from, but the copied database worked fine.

Then this morning, I noticed some weirdness in some of the RedisSession settings we use that I cleaned up and fixed that seemed to maybe help with the redirecting, but I'm not 100% sure.

So at this point I'm feeling better about the site, but since I don't know a root cause yet I can't say the issue is fixed. Anyone have any ideas about what might be going on or things that I could check that might cause the issue described above?

EDIT: Not sure if this is relevant, but the redirect issue just came up again to the point where everything was always redirecting to localhost. Interestingly, I flushed cache and session data in var/session and in Redis, and now the site is back without any problems. Not sure if it's related, but it made me raise an eyebrow.

EDIT 2: The issue came up once more yesterday and that time I put the site into maintenance and flushed the cache and sessions that I've got in Redis, the sessions that were on disc, and truncated the core_sessions table. That seemed to do the trick. The site came back up and I haven't seen anymore redirects since then. What's bothering me is that why would screwy sessions data cause the site to redirect like that?