Not saying this is the case, BUT most people are unaware of exactly how a given address is listed per the USPS database which some of these query tools use..
Example most people think or use:
1234 Any Street Boulevard
Actual USPS listing (likely used in queries)
1234 E Anystreet Blvd
Note the following:
1. Accurate directional
2. Accurate spelling (word structures)
3. No use of punctuation
4. Accurate use and inclusion/omission of Ave, Blvd, Pkwy, Hwy, etc (do not spell entire word unless advised in the USPS DB)
5. Accurate use zip codes (they do change without notice sometime, especially in new areas
This link:
http://zip4.usps.com/zip4/welcome.jsp
Will list current zip and correct address formatting.