"Geocaching does not use polygon data but just what the CO places on the listing"
that's a very important part, most people don't realise.
If the CO uses the wrong county/country here, it shows up wrong on geocaching and most of the other sites. Had a look on MyGCProfile FAQ, they seem to first assume GC is correct and only change it manually if someone send them an email about it.
The mentioned cache has its co-ordinates in NM, as clearly showing on the OSM. I have the PGC browser plug-in, which corrects listing data automatically.
But I looked up the map in Google and indeed, the border is far more to the east, placing the cache in Arizona. On the Esri DeLorme Map, the cache is placed right on top of the border. All depends on the map it seems.
PGC uses officical polygon data, so probably most precise.