What qualities should a Search Engine Optimization (SEO) company posses?

They should be the first hit when I google for search engine optimization companies, and they should be able to get me in the first 5 google and yahoo searches for my business parameters.
They would be able to prove to me with references of specific clients that I can search that tehy are better than the others and the clients should be willing to talk to me and give a glowing recommendation.

@Judi While finding companies that rank in top positions does seem like the most rational way of going about finding an SEO, it doesn’t necessarily make the company with those rankings any better than the ones that don’t. The reason I say that is because the best SEOs tend to rely on word of mouth and reputation over proactive marketing. Most companies reasoning behind doing this is based on the fact that the term SEO is very broad and brings in a ton of undesirable traffic, which makes it a very poor term for companies that look at SEO as a strategy and not just a blanket service that is the same for everyone.

@lincolnt10 here are some blogs I wrote a while back about good SEOs vs. bad, etc. Also a link to a really good SEO marketplace…

http://www.fgi.com/blogs/post.cfm/black-hat-or-just-lazy

http://www.fgi.com/blogs/post.cfm/5-tips-for-finding-an-honest-seo-agency

http://www.seomoz.org/marketplace

@drClaw , from a CUSTOMER who is not savvy enough to do it myself, that would be how I would judge if I had no other data to go on. He did say, “to gain your trust.”

The main and key point is that they have to deliver what they promise without effecting the quality.