In the past 10 years I have worked with several people who claim to be experts on SEO or with companies who say the same. I always found most of the strategies are not worth paying for. You can easily find these yourself with Dr. Google.
But recently I was hired by a company who need SEO for their business model. They are earning immense lots of money with a perfect SEO for their websites in combination with ads. I was working on a different area, but when I saw what they did, I was simply impressed. That company actually does not offer SEO consultation.
They told me that I was actually right: 95% (if not more) of the SEO people are always saying the same; this "knowledge" can be found on various blogs. But there are a few people who really create "strategies" which they apply. I think its more than "SEO". One of these recommendations was Karl Kratz. Unfortunately he does only have a german blog.
That said I think you should do the basic seo stuff you can find on the net. Then try to get into press and blogs. This is - for me - the most efficient way to be ranked.
I would only hire a seo company/consultant if I really trust him and he has proven some expert knowledge to me which I didn't read on the blogs before.
To answer you question, reputation does not necessary mean they can help you and your product. I might mean that they had some luck, because they had the right customers before.