Our company spent over $3mm last year and this article is spot on. On the Adwords side it really is that simple - test tons of creatives and use CPA bidding.

The third party services aren't much help. Google has a lot of great in-house support to ramp up your Adspend once you get noticed. Not sure what the target is, but we seem to get a new rep every few months who has new suggestions.

I have no experience with Youtube, but that is highly interesting.

If Adwords isn't working for you, there is a ton to dive into. Could be your website, could be your product. If you have a competitor obviously succeeding in the space with heavy Adwords spend the fault is probably on your end (unless they're just pissing away money, but how long does that go on for?).