I'm writing this from a throwaway HN account. I work for a 4-year old company, where I was one of the first 3 employees. We have a very popular website that gets over 400 million page views per month. We get lots of traffic from Google. When I started, our priority was making a great, simple user interface. But we were also very aware of SEO, and paid much attention to self-links we put on the site, anchor text, URL parameters, all the usual smart SEO stuff. So far so good -- we did this opportunistically, and never at the expense of the user experience.
As we grew, we hired a person dedicated to SEO (a non-programmer). Then we hired another. These SEO people started having us add links and pages in strange places that made no sense to actual users. And adding links that sometimes made sense to users, but were unnecessary, and cluttered the user interface. The page footer grew and grew, eventually spanning 3 lines. We added funny redirect schemes that made the site slower for users. We were afraid of our links to other sites because we might leak valuable "Google juice". We added redundant tooltips that were useless to users. Many of these tactics were crap our SEO people read on some webmaster SEO forum, with no scientific basis. Sometimes our SEO people even had the gall to say "I have an idea I think will be better for the user experience", and go on to propose something that only benefited SEO, and made the user experience worse! In other words, they would focus on GETTING the user (via Google), but forgot about KEEPING the user (through good user experience). Thankfully, we never did the black-hat methods like cloaking, but some things very close were proposed and met with loud opposition from our developers.
For a long time I would fight against these changes, because they made the UI worse. I lost most of these battles because it was hard to convince the managers that it was hurting the site (but it never seemed to be necessary for the SEO people to prove it was actually helping SEO). I was eventually spending so much energy fighting these SEO proposals that I just gave up. User interface designers and developers spend a lot of effort to make a web site look good and run fast. Then the SEO people go and fuck it up. It's very frustrating for developers. I know SEO is important. All I'm saying is that SEO should never be at the expense of the user experience. I hate what it has done to our web site, and I know it's happened to other websites as well.