Forum Moderators: open
Look for a company's track record. Check their current clients and ask for references. If they have large well known clients AND small clients that are both happy, they're doing something right. Look for results not promises. No one can guarantee or promise something they can't directly control.
We would all be happy to recommend ourselves as the best solution for your optimization haha ;)
Oh, and by the way, welcome to webmasterworld! This is the right place to learn about SEO!