No state either? Would they know which state to route that to? I think yours is the largest but apparently there are a bunch of cities in the US with that name.
The reason why the distinction of post offices is important is that zip codes are not required to follow state boundaries (technically, zip codes aren't an area, but a list of delivery points). In fact, there are a lot more than you'd think that span across state lines, so there may actually be a mismatch between the state for your address and the state for the post office your mail is delivered by.