After dealing with addresses for 30 years within databases, applications, creating and sending bulk mail, an so on, the postal code is key and in fact the only reliable data within an address. The reason is this. An address can be written any number of ways, but a postal code can only be written one way.
Why did I say this?
I wrote a CASS system years ago that validates postal addresses and certifies them for bulk mail. All bulk mail address must be validated as being 100% correct and certified before the U.S. Post Office will accept it. A major part of validating an address is the postal code. For example, how many addresses are on "Main Street" in the U.S.? How can I know that "this" Main Street has an address of 512? The postal code. It is impossible to validate any address without it. As well, from a DBAs perspective, since addresses can be written in a many variety of ways, the only key-able data that can be validated and trusted easily is the postal code. The remainder must either be trusted "as is" or validated using a CASS system or something similar.
So what does this have to do with SEO?
Do not think that Google is not validating names, addresses, phone numbers, etc. How does Google know that an address exists? Simple. The CASS system. CASS is the authoritative knowledge base of addresses all over the world and all of the global shipping industry relies upon it's accuracy every second of every day. If an address cannot be validated using CASS, it simply cannot be trusted.
If the postal code is missing from a address, the address is simply invalid and ignored. It cannot pass validation before being accepted as a critical part of branding. Google validates a sites address and creates a fact link within the knowledge base that ties the site to an address. The same happens with names, phone numbers, etc. As any knowledge base expands, a critical factor that allows a knowledge base to work is corroboration. All data must be validated before being accepted otherwise it is not a fact. If an address presented on a site cannot be validated, then a fact link within the knowledge base cannot be created. Going back, any address cannot be validated without a postal code. It is simply impossible.
It also is impossible to brand a site in Google without NAP, e-mail address, or other verifiable contact information. The site must be validated as trustworthy and being open about who you are is the largest part of trust. If your address, a critical part of NAP, is incomplete, then a fact link cannot be created within the knowledge base and branding and trust metrics as a result can not follow which are significant factors in search performance.
So in the end, not having a postal code as part of your NAP does effect search performance. If you are providing information on your site, make sure that it is valid, complete, and trustworthy. Otherwise, what is the point?
As for format?
There are several valid formats. Google has over the long many years perfected recognizing and reading different formats for the NAP. It is advisable to remain rather traditional as to be helpful. Since Google has studied how addresses and NAP are written globally, it is advisable to follow what is traditional in your area. Keep in mind that the knowledge base is used much like any CASS system's duplicate elimination algorithm base to validate an address, or other data element. DupeElim algorithms are highly effective and rather simple. They can ferret out just about any format of an address there is. Simply put, it is not rocket science and well understood. Much has been written on the subject and CASS has been around since the beginning of computerizing postal mail. Longer than many of us have been alive!
I will offer this.
There is a reason why schema.org mark-up exists. It makes passing data to search engines a more trustworthy process. Why? Because the data elements do not have to be parsed and guessed. They are defined. It is of a significant advantage to use schema.org mark-up for your NAP. In this way, you are partially eliminating the need for data parsers and duplicate elimination algorithms and format matters much less. Where-ever possible, it is highly recommended that schema.org mark-up be used for NAP.