Velcrocat,
If your outbound trunks are PRI, you might want to check on what your helpdesk agents are displaying on outbound trunk calls.
When we had our trunking changed to PRI a number of years ago, I did some testing on what would be displayed for various different scenarios. I found that sets with DDGD in CLS would show as "Private Name - Private Number" or something similar, and phones with Anonymous Call Blocking set up would block the call.
I got around it by setting up a CLID index to show no number (HLCL is null, and DIDN is NO). With that CLID, the calling number shows as "Unavailable" on a Caller ID display. Not the best, but the call gets past Anonymous Call Blocking.