I searched the USPS web site, queried GeoData.gov, did a general Google search and turned up nothing. I tried querying GNIS for feature type post office, but the data is listed as "entered 1993" for most entries, and just looking at some in my general vicinity I can find now-closed post-offices not listed as "historical", currently open post offices listed as "historical", and open post offices with locations listed as unknown. All in all, not a very good approach.
While a national listing would be ideal, a source for just New Mexico would suffice (at least for now.)
Best Answer
One possible data source is the POI Factory. They have a post offices layer (I don't know the quality of the data) that purports to have
Depending on your planned use, you should definitely read their Terms of Use.