I'll say this about banner ads on websites - they need to be really closely linked to the content and have a call to action if you want to get clicks. Otherwise it should probably be viewed as a brand building activity.

And that's probably one of the challenges when it comes to online ecommerce - very few operations recognise that it takes time and repeated exposure to build a brand name. Most want instant results now!

Well, if it's instant results that you want, Google Adwords for search and plugging into existing shopping sites is probably the only way to really achieve it.
Unless you manage to pull off a viral campaign, which is a lot easier said than done.