Dating sites are a really bad counterexample, since they have to advertise(except plentyoffish and OKCupid, which are also free) and TV advertising for an Internet business is a sure sign of a failing business. (Think about every search engine you know. Almost every single one has tried to advertise, except Google. Google never ran ads. All their competitors did.)
I'd be curious to hear in what sense you consider online dating sites failures. Your assertion that advertising in other media makes them a failure is, well, just that; an assertion. I don't have any numbers on the financials of the companies, but the general consensus of people that I know is that OKCupid is a fine place to waste time, but that if you really want to meet people you need to go to the pay sites (precisely because the financial barrier-to-entry keeps away all the people who aren't really interested in dating).
I've heard that okcupid is an excellent way of meeting new people you actually like -- from friends that use it like this. My short time on there seems to corroborate this.
