There's no question that whitehat SEO pays off. And referring to startups, you mention "I struggle to imagine a situation where smart people just can't read up on it themselves and execute it themselves."
It has everything to do with your opening line: "We've spent a lot of time doing whitehat SEO on our website".
It always comes down to TIME. If you're a new startup, you're trying to work on your business, not in it.
Then you need to find someone who can help you with whitehat organic SEO. And as you mentioned, the hard part is navigating your way through the 'quacks'
Most startups as far as I know don't have much money, but if they do have money then fair enough they can spend it on SEO if they think it would be beneficial. As you say though it's going to be hard to find someone decent and honest.