Opened Trac Ticket # 3838 about this. Please vote follow if you have the same issue.
It would seem that Nominatim has no support for zip+4 codes in US addresses. While its understandable that it cannot return a zip+4 zip code, adding a zip+4 to an address will cause the geocoder to not match an address that it would otherwise match.
Yes this is appears to be a bug in Nominatim, and should be submitted as a bug to: trac.
Please be aware that Nominatim itself is down currently due to unforeseen scaling issues (there's too much stuff in OSM!).
And what you see may in fact be an artifact of that fact.
Zip codes are complex things, they have to be placed on every POI, especially the +4 zip codes, and it's well known that (sadly) throwing more data at Nominatim can make a good search fail. That is given more data, Nominatim can sometimes return no result, rather than the expected behavior.
That's unfortunately a long standing problem, and unlikely to be solved in the short term, but I'm sure the Nominatim developers would love more help.
answered 18 Jun '11, 23:18