I also agree that the problem is most likely at the provider.

I'll try to help with some basic background from the translations side (at least with the 5ESS).

The way in which a call's digits across PRIs can be stripped and replaced by other digits depends on the direction of the call:

Calls outbound from a CO-
This is handled within the route index assigned to the PRI which handles the call "from" the CO.

Calls inbound to a CO-
This is handled by the IDP (individual dialing plan) assigned to the stand-alone PRI (or an entire PRI group) which provides the call to the CO.

With this problem occurring on a 3-digit call "inbound" to CO, it's very possible that the CO folks may have accidently assigned an incorrect IDP to the PRI's BRCS features list. IDPs are customized features that can be assigned to stand-alone PRIs (and PRI groups) that dictates and performs stripping (and replacing if needed) of certain digits inbound to the CO across that PRI. 5ESS IDPs are built by using multiple "ranges" to specially treat specific inbound digit patterns. If the CO uses a 5ESS, it sounds like the fault may be that either the IDP is assigned but not activated, has an incorrect range assigned for the inbound 411, or has an incorrect IDP assigned all together.

I remember an instance where an inbound PRI Group from a local PBX had an incorrectly assigned IDP. All calls placed to a specific local prefix were mistranslated, sending these calls flying halfway across the country.

Do you have access to, or is there any possible way that a PRI tester (Sunset, etc) can be setup to place a 411 test call directly across the PRI?