You said it only happens on LD calls.
Are these calls going out the same trunks as the local calls?
If yes, I'd start pointing at the carrier. They will need to do a trace while you duplicate the failure.
If no, it's possible you have a trunk issue or turnk port issue, but I'd still doubt it unless the calls are being routed between one or more PBX's.
Ralph