Hm. They complain that they couldn't contact Google about this, yet it only took me a minute or so to find: "To request reinclusion, log in to Google webmaster tools, click Tools, then choose the Request reinclusion link and follow the steps outlined there."
Perhaps they did that and just didn't mention it.
There's a lesson here: don't depend on a single factor you can't control.