We've spent a lot of time doing whitehat SEO on our website, and it's paying off (2x search traffic in 6 months). I really would recommend most startups spend a few days reading up on it from good quality sources. Nearly 40% of all our traffic comes from search so it makes sense to pay it some attention.
It's not hard. What is hard is navigating your way through the crooks/spammers/quacks who will try every trick in the book to try and sell you something you don't need. Startups do not need to hire experts to do it for them. What they need to do is solve problems like they solve other problems, with no money.
People who sell SEO usually:
- Have the gift of the gab
- Prey on peoples ignorance
- Prey on peoples greed
There are good SEO people out there, but they are rare. Also I struggle to imagine a situation where smart people just can't read up on it themselves and execute it themselves.
As a startup you should be focusing on good quality content and sustainable growth. So play to your strengths and don't pay a lot of money for magic potions that offer short term benefits. Play the long term game.
SEOMoz is a good place to start (their free blogs etc). Executing good technical SEO on your own website is pretty easy.
Tibbon made a good point, 'dont do SEO do accessibility`. I'm not sure I'd go to that extreme, but it's a good way of looking at it. Google is your most disabled user, it can't see very well, it can't really understand things very well either. If you make your site highly accessible you're well on your way to good SEO.
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.