Here is how I recovered one of my domain - True Story!
My domain resolves only for www.domain.com and has 3 subdomains (sub1.domain.com,sub2.domain.com,sub3.domain.com)
1.I removed all outgoing links from all the pages of domain and subdomains.
2.In index page of www.domain.com I put links to all indexes of subdomains.
3.In every index of subdomains I link back to main index of www.domain.com
4.In webmaster central (sitemap) account I fix all the problems reported in the not found section of index summary.I made a 301 redirect to existing files or remove the link to them (2 in my case),in pages of domain or sub if pages not anymore.
5.I look at 22.214.171.124 performing this search:
Notice there is no punctuation between domain and com.
In this DC everything was OK.Links was listed ordered by PR .
6.In other DC's there was no correct listing in first spots being sites who have links to my domain or subdomains.
I emailed only those webmasters to which sites I had links at pct.1 and ask them to remove those links.
In every day there was a progress, things geting closer to what I saw in 126.96.36.199 .
Now after 51 days I'm back in a better position than before.
Wish You all the same.
Please contribute with your own experiences.