I've got something I've always been curious about. If the website was penalized by Google, is it possible to rank _after_ the penalty is lifted?

Edit: the story behind this question. A friend of mine has a local business. He once paid an SEO agency to do optimizations for his website. After a while, the website was penalized because of some shady stuff the agency did (paid links?). The penalty is long gone, but it looks like Google never forgets anything, so the website is sitting there on 5+ pages for pretty much any keyword.