This is a sorta long standing problem of nominatim, not OSM data as far as I understand.  Zip codes zones are not stored on OSM, just individual objects.  The problem is that nominatim seems to "guesstimate" the zip code based on proximity to objects that have a zip code, which fails when you're on a boundary.  Best can be done is add zip codes to objects so that it sways nominatim to do the right thing...