I have never heard of such a thing. However, I once had a site dropped from Yahoo, but after getting a few high quality backlinks, it reappeared after 6 months. I am not sure if it was a coincidence or not, but perhaps if you get a couple of authority backlinks and wait a while it might automatically get reincluded.
Thanks guys. I submitted it to the url you suggested. On a side note, I do believe it has to do with inlinks. We actually had two penalized. The one in which we "got" a bunch of links ranks #1 for the target keyword, while the el-natural site with pure content ranks badly, so I submitted the request just in case. The domain is in the index but nowhere to be found for its keywords.