Some ISPs have provide a service that redirects your browser to one of their search pages when you type a host name that doesn't exist in your browser. This relies on catching all DNS requests that wouldn't normally resolve and send one of their own IP addresses instead.
Try typing the incorrect name in a web browser (from the network where you've found these issues) and see what you get. It may just be a page from the ISP; you may also be able to find some explanation in the corner of the page, and be offered to opt out.
There is a link for a specific ISP (from Wikipedia), which describes their policy: http://www.optimum.net/Article/DNS.
It's not a great practice, especially when you can't trust the page you're redirected to, but if this problem is indeed specific to a given ISP, it's not a problem with your DNS server. In this case, there's little you can do apart from trying to opt out from this "feature". This is more a problem for your users than for your company, but there's little you can do if they can't trust their ISP at least to resolve DNS correctly (some will also prevent you from using external DNS servers).