I haven't seen an issue like this in all my... well, 6 years of doing websites.
I have a site that has been pretty popular making it all the way up into the Alexa top 15,000 for what that's worth. It's been going downhill due to bad code and db build that makes it crash when I get more than a few hundred users online at the same time - that's not the issue, just a bit of background.
The issue is that the site was PR6, even had the Google sitelinks display in the SERPs and was humming long. Today it's PR 0 and nowhere in the search results for anything other than one lonely page that says the site is offline (but if you click it takes you to the site).
Things have stayed this way for months. I go to the Google cache and it does indeed show a site offline page.
The funny thing is, the site isn't offline and never has been for more than perhaps hours at a time as far as I know. The site is clearly up and running and doing over a million page views a month. All based on brand recognition (as it really can't be found in the SERPs and I do zero advertising for it).
I have no idea what's going on and why the issue is not correcting itself after so long in the search engines. I don't know where to turn. I've done a re-inclusion request, but heard nothing back. I've showed the issue to others and no one can figure it out.
Here is what I know it's not caused by:
1) Penalty - How do I know this? a) There is nothing we're doing to be penalized for and more importantly, b) It's the same story in Yahoo and MSN - they all think the site is offline.
2) It's not a misbehaving robots.txt issue.
[edited by: tedster at 11:38 pm (utc) on Jan. 13, 2009]