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.
However, spending time does.
Most of the big wins on SEO are a combination of strategy and time. As in : have a strategy to get links, and spend time on that strategy.
Sure, you can pay someone to do this for you, but anyone who is smart enough to develop software is more than smart enough to do SEO.
The big mistake people make is thinking it exists outside of marketing. In fact your SEO strategy and your marketing strategy are just two dishes on the overall meal of gaining customers.
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'
Also your post smells exactly like the sort of sales pitch people seeking SEO should try to avoid. Big grandiose speculative statements.
"Grow 6 inch...errr times, or your money back! Real SEO!"