Like anything, companies figured out they can charge you for whatever add-on as long as it didnt disrupt potential income. There is definately some overhead associated to this charge (software upgrades, more complex so customer support, etc.). Everyone charges this fee and the market has absorbed it. Technically it doesnt add that much since sat service has detailed programming guides but until someone breaks the standard, they will charge a fee.
I think the combo D* and DVR fee is much better then getting a seperate Tivo. 5 or 6 bucks I can live with versus $13. You can always get a Windows Media Center that has no monthly fee. Unfortunately, combo service units are the only ones that can natively record non-OTA HD programming. Stay tuned for cablecard devices but those will be coming with service fees like the Series 3 unit from Tivo.