Mind you, what those providers generally do, is "poisoning" DNS.
Their DNS servers will return their "helpful" search page everytime they cannot do a DNS resolution.
If your provider cannot be configured to turn this off (Deutsche Telekom for example allows this), the solutions is relatively simple: Use another DNS Server. If you cannot set one on your router, you can at least do that on each device.
On the other hand, if your provider *really* has the ability to intercept 404 messages from websites, even on HTTPS sites, that would mean they are actively looking at the sites you visit, and if they do that for HTTPS, they are running SSL decryption. In those cases you cannot assume any privacy and should switch provider, or use a VPN if you can.