Unfortunately, this seems to be a consequence of how Media Center deals with guide data when new channels are added or changed by the service provider. Perhaps I am wrong, but this is what it sounds like to me.

I have been using Dish network for the past few years and it is probably even more annoying since if Media Center attempts to tune one of the unsubscribed channels that magically appears in the guide, the set top box needs to be messed with to get it back to normal. I make a point of going through the guide and cleaning away the garbage monthly or bi-monthly.

Here's something to try that I picked up from using HDHomeRun. In Windows 7 Media Center, it periodically scans for updated QAM channels, but you can disable it without consequence until the next time you need to initiate a scan during TV setup. Open regedit and find the following: "HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Media Center\Service\BackgroundScanner". Then, create a new DWORD value named PeriodicScanEnabled set to 0. Close regedit and reboot.

I use Guidetool to delete the channels. It should remove them from the Media Center database completely. So far they have not returned.

Not really an answer for QAM yet (though coming) but DVBLogic's DVBLink software allows tuned channels to be permanently deleted before media center even sees them.