Has anyone had success with using a SEO company? If so, which one(s)?

I think one of the things to really note here is what kind of service you are after. Most SEO clients are not "the website is the company" businesses.

Type One

The client is a plumbing company. Their website gets 300 visits per month resulting in about a call a day. An SEO company can come in, get them to make some changes. Make sure Google can index all the pages, add meta tags, get some more content written, sort out local business listings, get a few links and bring that up to 900 visits and 3 calls a day. I would (and do) call that success. For comparison, the difference in cost between a Yellow pages ad that gets a plumber 1 call a day and one that gets them 3 calls a day would be (very roughly) $10k-$100k where I live.

There are lots of companies that can and do achieve this kind of success with decent predictability. They can usually do this without too much reliance on the client for input. Sceptics will point out that you coud get SEO for dummies and do this yourself. SEOs point out that most plumbers don't. Anyway, this is most of the SEO "market."

Type Two

There are also the kind of SEO companies that advise bigger companies on their SEO strategies. They work with IT/Web on creating more SE friendly designs. They work with content writers on selecting topics that get searches. They run training sessions on metatags and giving your page an "on page SEO score." These companies' expertise is mostly consulting expertise. There is some specific knowledge they bring to the table, but not rocket surgery and not really more than the other type of company, usually. I reckon you could train "SEO Consultants" in weeks. What they do do well (if they are good) is they are able to get these companies to change the way they do things a little. These probably have as much in common with "occupational safety consultants" as they do with the former type. If I was hiring for these businesses, that is the background I would be looking for. These projects probably have a higher rate of failure since they require changing the way an organisation does things.

The kind of people that write blog posts about SEO companies however are very rarely in these categories giving the whole "industry" a warped public perception.

I think many businesses on HN should be doing their SEO in-house rather than contracting out. My reasons at length:

http://www.kalzumeus.com/2008/01/28/why-you-shouldnt-pay-any...

There is also the factor that to be good at SEO, really good at it, you have to integrate it into your ongoing operations. It is like marketing: you can't put a firewall between the product and the marketing and just toss stuff over the wall and expect it to work.