Why does a Coding Application say a 5-digit ZIP Code is valid, but MailStream Plus says it is invalid. Or vice versa.

MailStream Plus™ all versions, all platforms
The cause is that the Coding application's database is different than the one the Presorting application is using.  

The USPS does add and remove ZIP Codes regularly.  
The databases the USPS provides for Coding software to use comes from a different part of the USPS than the database they provide for use with Presorting software. The two USPS parts do not add and subtract ZIP Codes in sync with the other part. So even when using the same month's databases, they can be different.
Although the problem can be *minimized* by using the same month's data for both types of applications. 

Also, the databases Coding applications get and use is designed to match addresses to their ZIP Codes.  The databases Presort applications get and used are designed to provide the information to presort mail based on it's ZIP Code.  They can be different for valid reasons.

For one example, in July 2015 there were 15 ZIP Codes that started with 569xx.  They were assigned to the USPS's "PARCEL RETURN SERVICE".  (The Parcel Return Service is used to allow consumer recipients to *return* merchandise/parcels to merchants without having to pay return postage.  So a commercial mailer should never be presorting and mailing anything *out* to one of those ZIP Codes.)

Coding applications-
According to the USPS database that coding applications use, the 569xx ZIP codes are valid ZIP Codes. They are listed as 'Unique ZIP Codes'.  Unique ZIP Codes we normally think of as used for college addresses, or large corporations, etc.  i.e. places that get a whole 5-digit ZIP Code assigned to them.  And the company or whatever is responsible for the actual final delivery of mail within the ZIP code.
For Unique ZIP codes, *any* street address is acceptable, *and* any address in a Unique ZIP Code is considered to be 'deliverable' per the DPV processing.
That is why Coding applications will say such ZIP Codes (and the addresses are valid.)

Presorting applications-
MailStream Plus™ uses different databases from the USPS, which include info about how the different 3-digit ZIP Codes are to be presorted on the way *out* from a mailer.  
When you look up the 3-digit 569 in MSP's databases it shows as invalid.  And 569 is not listed as a valid 3-digit ZIP Code on the USPS's Labeling Lists used in presorting, such as L002, L003, L005, etc.  Again, because no mail should be presorted and be going *out* to them from commercial mailers.
UPDATED:  May 23, 2019