I use CPC advertising almost exclusively, although I do advertise in a couple of magazines also. I use Google, MSN, and Yahoo. Nearly all of my new customers come from these ads. I wouldn't be in business without them.
That said - I spend a LOT of money on advertising - by far my biggest expense. You can budget what you spend by ad campaign - so if you want to try it out and test it you can. With Google I don't have much limit set and spend hundreds of dollars a month. With Yahoo I have it set at $50 and add to that when it runs out - usually once or twice a month. I just don't get the traffic on Yahoo and MSN ads that I get with Google.
I also really like google analytics a lot. It's not perfect - but it gives me a lot of information.
One thing with the CPC - you may not be able to compete on the common keywords- so look for less common ones that you can get very cheaply. Also try common misspellings of words.
I don't know how an online business can go without CPC advertising - unless you are very high in the standard search rankings. I was on the first page of Google for many of my keywords before I switched to 3dCart. I'm hoping to work my way back to the top over time. That was one of the only bad things about switching carts.
Good luck
Cekman
www.cobwebcorner.com