Do you have a Google Webmaster Tools account? If so, login to see if there are any unnatural linking penalties. To my knowledge, over-optimization is not going to get you kicked out -- a lower ranking maybe, but completely de-indexed seems a bit extreme. Now unless you completely overdid the optimization thing, it could be something else.
So you did a search for "yourdomain.com" and nothing from your site shows up?