Can you elaborate on how your calls egress to the PSTN? Do you have multiple points of exit?
You can use either use Calling Party Transformations on CUCM (applied at route-pattern/route-list/gateway-trunk level) or Translation Profiles at the SIP/H.323 gateway.
Georgios
Please rate if you find this helpful.