What needs to be done to have ISPs and other service providers stop tampering with DNS ?
Some options:
Contact your local, state and federal legislators and convince them it's in the public interest for them to draft legislation to outlaw this practice - and hope among all hope that the end result resembles something technically benevolent.
Do we really want big brother sniffing around ? What about net neutrality ?
Contact ICANN/IANA and plead with them to stop assigning any more resources to said ISP.
ICANN has no contractual relationship with the service providers abusing the DNS, but a far reaching idea could claim ICANN responsibility and commitment to preserve and enhance the operational stability, reliability, security, and global interoperability of the Internet, stated in one of its core values on its bylaws.
Publicize what said ISP is doing and let its customers decide if it's a significantly deplorable enough practice for them to find another ISP.
Well Time Warner/Road Runner does it at least here in San Antonio, at least the don't filter DNS traffic if you choose to use other name servers and don't have a nasty proxy like the guys from Telefonica in Argentina. Anyway some of this nasty behavior will go away when as Mark said DNSSEC is fully deployed (someday). Regards Jorge