Over-Optimization Penalties

Many webmasters think that the engines can penalize some sites which "try too hard". The theory is that if you've got your money phrase all over the place -- in the <TITLE>, <H1>, <H2>, <H3>, <B>, and <I> tags, ALT and TITLE parameters, domain, subdomain, directory name, and filename, and it's repeated several times throughout the page, and it's the only link text that other sites use in their links to you, then the engine figures you're making a blatant attempt to cheat and they wind up pushing your site further down, rather than further up. And while the engines rank pages, not sites, it's believed that some penalties apply to a whole domain, not just to a specific naughty page. Whether over-optimization penalties really exist has been hotly debated in online forums with a lot of convincing arguments and evidence each way. My feeling is that such penalties do exist, but that they're not applied consistently and that it's difficult to tell what triggers them. But to me there is little doubt that they get applied sometimes.
Here's an example: In a Google search for "cheapest airfare", only one of the ten results contains that exact phrase in the title! This is a competitive term and there are obviously many sites vying to rank well for it, so it's inconceivable that only one high-PR site is using the term "cheapest airfare" in its title. That means that sites which use the search term in their title are out there but not ranking well. This is strong evidence that Google has penalized them.
When I first noticed this particular case my first reaction was to assume that Google was penalizing pages for no other reason than that their titles contained the exact search phrases. But remember that this violates one of the primary points mentioned in the Myths section earlier: It is nearly impossible to discern cause and effect, especially at first glance. Stepping back a bit, it's easy to come up with another plausible explanation for this phenomenon: Google might not be penalizing pages because their titles were too specific, but rather because their titles were too specific and that same search phrase was repeated throughout the page in an SEO-like manner. It could be that Google doesn't care if a title has the exact search phrase, as long as that same search phrase hasn't been stuffed everywhere else on the same page (and in file and directory names, and in link text, etc.).
How can we tell which is the case? Or if it's something completely different? We can't -- not easily, anyway; not without a great deal of research.
So how to deal with this? Here are my recommendations. For the title tag it's simple. Search for the phrase you want to rank on. If the results use that phrase in the title, then you use it too. If the top results don't use that phrase (and you know it's a competitive enough phrase that there are sites using it in their title who aren't ranking well), then do like they do and use a variation of your preferred phrase rather than the exact phrase itself. Just be careful and don't automatically assume that a lack of pages showing the exact search phrase in their titles means that the engines are discounting them; it could mean that you got lucky and found a search term that doesn't yet have a lot of competition, and that there aren't many other pages yet using that search term in their titles, or it could mean that the penalty is not for an exact match in the title alone, but an exact match in the title combined with more matches in other places on the page.
For other factors, I suggest using the on-page factors as you normally would, just don't use the same exact phrase in every single place. Once your PR is similar to the sites you're competing with you should be near them in the SERPs. If you're not, then it could be time to consider modest de-optimizing at that point. But in general, I don't worry about de-optimizing unless there's a page I can't get ranked well normally after several months.
Incidentally, my site is one of the top ten on that search for "cheapest airfare", but without using the exact search phrase in the title. I changed my title to include the exact search phrase, and a couple of weeks later I went from #3 to #8. Of course, I couldn't be certain that it's a result of my title change, though. Still, I changed my title back to the original to see if I'd move back up, and I bounced back up to #4 pretty quick. While we can't draw any definitive conclusions from this, it suggests that having the exact search phrase in the title tag might have hurt my ranking in this particular case. For most pages it's probably still a good idea to have the exact phrase in the title, changing it only if good rankings can't be achieved, and if the pages that are beating yours don't use the exact search phrase in their title tags, either.