Stop it, really.
The way in Search Engine Optimization the term "over optimization" is used is an oxymoron, it doesn't make any sense.
An example of proper usage of the term
In some areas the term "over optimization" is used to indicate when the increased benefits to optimize something do not justify the increased cost, effort and complexity to obtain it.
For example, suppose there is a software product with a button to perform a certain operation. If after clicking on the button the operation takes – say – ten seconds or more to perform, with the interface frozen and not responding, user experience would be really bad.
Let's say you are the computer programmer in charge to optimize its performances.
With a quick at the code you spot an easy optimization, suppose you realize a costly operation was repeated unnecessarily twice in a loop; with just a minor change you half the execution time.
Great! Almost no effort, and a great gain. Nevertheless, 5 seconds are still an unacceptable response time in terms of usability, so you try a little harder.
You understand that using a different data structure to store temporary data you could gain much more when you have to look it up, so you "refactor" the code, and get a 1 second response time. Much better, but still way too slow to give the perception of a responsive program.
You then realize that using a more complex but well known and documented algorithm the same operation could take much less time. So you implement it, and the whole operation now takes one tenth of a second. That is generally an accepted threshold for a synchronous operation, as response time of 1/10th sec or less are perceived as immediate by the user.
After half a day of coding, and some effort, you have reached your minimal goal and could repute yourself satisfied.
…but you got excited now, and wonder how far can you push with optimization. You start studying you algorithms, new data structure, new design patterns.. and after another half day you realize that by changing the backend system, changing the database version, adding an additional and expensive caching systems [… and so on…] with a good month of work you could go down below 1/100th sec.
Then you boss steps in: "Stop!"
(You should have actually stopped half a day before, but that might be an investment in knowledge so she turned a blind eye).
You would not work in your company interest: all those changes cost development time, testing time, licensing costs, they would make you ship your next release months later, lose market opportunities, etc… In order to obtain a negligible benefit (in terms of overall gain), you would have unacceptable additional costs.
You are “over optimizing”.
That is a case where the term makes sense:
You are actually optimizing something (response time, from 1/10th sec to 1/100th sec), but the increased cost does not justify the effort.
You are going toward an "ideal goal" (e.g. zero response time) but after a while the return of investment are not worth the effort:
Effort (x-axis) vs Benefits (y-axis) in a real over-optimization case
Going further with the optimization would get you closer to the ideal asymptote, without being able to pass it (in the response time example the horizontal asymptote would be zero and the curve decreasing: you can lower your response time, but not below zero seconds, and the benefit would be negligible because no user would notice it).
The way the term is used in Search Engine Optimization
In SEO world, the term "over optimization" has become an oxymoron:
You actually cross a threshold where additional effort damages you. So it's not an optimization, is making something worse. You stuff far too many keyword repetition to the point to make the text hard to read in the hope to make improvements in search engine rankings, or you spam "build" thousands of links because you were told "the more, the better", all with an exact-match anchor-text no savvy webmaster would ever use because you want to rank for that search query… but all you get is falling down the SERPs, or being wiped out of the search engine results altogether.
Effort (x-axis) vs Benefits (y-axis) in a so-called SEO over-optimization case
You didn't (over)optimize, what you did is shooting yourself in the b… foot.
So stop using the term "over optimization".
Comments are open on linked Google+ page.