I can't say I have ever hired a company to work on my SEO for me. Any SEO that has been done has always been done by myself and as much as it does take longer to see results, I find that it's worthwhile to see all the hard work pay off.
It would be interesting to hear from others who have used them though.