My take from the provider side-
Can you ask your provider if they're using 5ESS? If they are, ask them if they can please run a "Verify Office" [VFY:OFC,DN=XXXXXXX, DIALED DIGITS=XXXXXXX] command to get a full detailed end to end report of the call's treatment. They should also be able to run an IPCT (in-progress call trace) for you to see exactly why you're receiving "their" (keyword) recorded announcement. Since it's their announcement, they should be able to explain why you're receiving it. And if they are 5ESS, the above tests should give them the "WHY" to provide back to you. Hopefully, the provider can be very helpful from their side with this symptom. You're right, dans, this is a headbanger.. :bang: Remember: Even though you are receiving the "that is not a working number" announcement, that is still considered a completed call out at the telco (it's just being routed to their announcement system for a specific reason), and no matter what system they are using, they should be able to tell you why the call is not processing to the fax machine.
