Please note that not all DNS requests originate from a browser. You are mixing DNS and HTTP, so intercepting and changing DNS will only aggravate your non-browser users and won't produce the process flow you want, hijacking the users browser input and sending it off to a search engine.

I think the HTTP proxy idea is the best, turning all 4xx responses into search queries. But I think that this will confuse users much more than just setting their homepage to a search engine.