A few days ago, I talked about a site that finally got indexed by Google after 6 months of owning the domain (presumably after having a penalty lifted). Today, I listened to the interview with Matt Cutts (download it from /www.webmasterradio.fm/episodes/index.php?showId=26). Most of the interview was the standard blah, blah, Google cares, blah, blah stuff, but the one little snippet that interested me was when Ms. Write (Sarah MacKay) asked Matt about penalty time periods.
Matt used the example of hidden text, which is generally penalized for a period of 30, 60, or 90 days. However, if some fancy javascript was used to hide the text, indicating deliberate "cheating", the penalty could be even longer. So, if you suspect that you have suffered from a penalty (rather than a simple algo change), clean it up, and get in your reinclusion request asap. The penalty time-out box won't get any shorter while you deliberate about what to do.