I had a site on a host that was having problems. The error log showed that Googlebot had received some strange error messages. I couldn't work out why and the hosting company was less than useful. Then the site got dropped from the index, completely, and googlebot stopped visiting for obvious reasons.
I moved to a new host, opened a WMT account for the domain and put in a re-inclusion request.
The form this took was.
1. A description of the problem I had identified.
2. What I had done to rectify the problem.
3. A pleasant but not grovelling request for re-inclusion.
Within 10 days I was back in and, having added a sitemap, and some new content I'm now back at #1 for all of the terms I am targetting and a few that I'm not.
IMO, if you are confident that you have identified the problem and have completely fixed it and after a period of time nothing happens, then, at least for me it was worth taking the plunge.
< continued here: [webmasterworld.com...] >
[edited by: tedster at 5:44 am (utc) on July 1, 2008]