Pretty much every state charges for some data and not others.

The USPS itself is a quasi-government corporation, so it probably functions under a different set of laws. I know that they will sell you a list of all the addresses in the US for a price. I've never thought about doing a FOIA request. You can try?