I too experienced this problem, and discovered a very simple solution - just stop using Verizon's nameservers.

Verizon isn't so much redirecting typos, as it is 404 (page could not be found) errors. This means any time you access a non-existent file on the web, Verizon routes you to their search page.

Through FIOS you receive a basic router with a web-accessible admin panel. By simply changing the nameservers in the router's configuration, from Verizon's to a third-party set of nameservers, the redirect service is eliminated, and you will never again be bothered by Verizon's redirecting service.

Click to read the article this is in response to.