I think a more accurate adage would be that if companies can get away with ads (or gathering and selling personal data), then they will do so. Unfortunately it would appear that giving money directly to service providers does not actually protect you from such things, and I suspect the reason is fairly straightforward: All companies are driven to increase margins as much as possible, and will eventually feel financial pressure to try such measures. Unless consumers object strongly (i.e.: leave the service in numbers large enough to offset the benefits of a measure under consideration), such measures will in general find their way into use.
So what we're really saying is consumers need to pay companies more than the money would get otherwise. If consumers aren't willing to pay that price (and it shouldn't surprise us if they aren't---this can be a lot of money), then we shouldn't be surprised if such things show up, regardless of whether the service is paid or not.
That's mostly a myth. The original purpose of cable was to get TV signal in areas where broadcast didn't go. The first basic cable channels were TBS--which had advertisements--and Christian Broadcast Network--which probably didn't. The unfiltered cable stations, for the most part, had advertisements.
You are likely remembering HBO, Cinemax, The Movie Channel advertisements. They didn't have advertisements because you had to pay per channel.
And what will stop them from running ads on top of that anyway?