Picking best SEO vendor

We have an existing open bid on SEO services posted at: http://www.getafreelancer.com/projects/49934.html and need help picking the best provider.

Any suggestions? Anybody used any of these firms? Who has proven to be most effective?

Any way to hold them better accountable?

I would ignore all bids offering delivery in less than 6 months. We generally say 6-9 months to our clients, but we add that if their keywords are competitive it will not be cheap and could take 1-2 years. There are so many factors that are outside of an SEOs control. How competitive are the keywords, search engine algorithim updates, how aggressively is the competition optimizing their site, etc. I would narrow it down to 3 or 4 by checking references diligently (contacting these sites and asking them about specifics), doing internet research on the companies like using the Wayback Machine ( http://www.archive.org ) to check how old their site is. Ask for other professional references. Google search their company name and look at more than just the first page of results to see if anything negative comes up. Once you have it narrowed down to a few companies ask them all for detailed proposals asking what they are going to do for the money. Then compare them and see what each is offering that is the same and what is different. If you have questions about what something is in a proposal post your question here. You can use this to ask educated, probing questions to each about their proposals. This will enable you to weigh service level against price in making your final decision. Good luck!

You can find a list of companies and individuals recommended by rand http://www.seomoz.org/articles/recommended.php