<rant> My experience with SEO companies has been horrible.
I worked for one for a month, have worked with them in the past at agencies I have worked at, and was given a list of "optimizations" from one a the startup I currently work for.
My experience while working for one is, by far, the worst. The owner/CEO asked me to lie to a customer and tell them I did work that he had actually outsourced to India. "In the future, try to funnel these things through you. Instead of saying, 'I will pass that on to the developer', say, 'I will take care of that'".
I feel like their skills are hard to quantify, and because of this a lot of people get sucked in on questionable sales pitches. This market then seems to draw the "Snake Oil" type salesmen who find they can get easy money.
Although there are good people offering quality SEO services, I have had 100% bad experiences with them. </rant>