Well, I wouldn't hold your breath either. As detailed in another post in this forum, I contacted Inktomi a couple weeks ago, via three different support addresses, about the same time I contacted FAST for the same thing. FAST responded and "unblocked" our domain within 24 hours, after realizing there was never any reason to be penalized. All I got back from Inktomi so far, was a form letter saying they won't provide (even paid) consulting on website submission.
Might as well scrap the domain and start over in my opinion. It'll probably be a lot quicker. The only thing I'm concerned about is 301 redirecting the old one to the new one to get the 1000's of valid backlink credit. Will this cause them to associate the old with the new and carry over the penalty anyway?