Holy cow, I wrote a book!
It looks like
Verizon's default DNS server for their customers
is redirecting all failed DNS queries to their own site,
calling the feature Advanced Web Search.
they have instructions on how to opt out.
The short version:
Go to your DNS settings and change the last octet from .12 to .14.