Similar story -

Kevin, one of the founders of Wufoo, does a great job of explaining how he grew the product by word of mouth. He built it from the trust of his users, most of which was from http://particletree.com/. It's fascinating how much emphasis he puts on interacting personally with the paid users and how they scaled that. Definitely a lot of hard work, but it paid off when they had some server trouble when Wufoo first launched - their old users trusted them and backed them up when some of the initial comments were negative.

Long story short, he didn't do any search advertising either.

Interview here: http://mixergy.com/wufoo-kevin-hale/

I don't think it's a coincidence that Dropbox took off just as smartphones became popular. People use a service like Dropbox because they're juggling more than one device. Dropbox has the advantage of being available on every platform and integrated into a ton of apps. Even if they weren't awesome on their own, Dropbox is the only service that makes sense now because none of their competitors has anywhere near the same network effects. Apps are their best marketing now.

Who am I to question the Dropbox CEO, but... Even if the solution is new, if you're solving a real problem that people have (and if you're not, what's wrong?), can't you use the search terms around that? E.g., "how to recover lost files", or "increase disk space", or "share files", or whatnot... Just get people at the point at which they're experiencing the pain you're addressing... No?