Have a CUCM 7.1(5) box with 2921 H323 gateways and PRI's to the PSTN. I have set my external Phone number mask to the standard format AAABBBCCCC. When I tell the route pattern or route list to use the phones external mask I see the Calling party as AAABBAAABBBCCCC when it is leaving my gateway to the PSTN. I see the same thing on both gateways and all 4 PRI's. If I hard set the CallerDN on the gatways in CUCM I get AAABBAAABBBCCC when the call leaves the gateway to the PSTN. Not even sure where to start looking at this one.
Sounds like there is a possibility that you are prefixing digits on the calling party IE at the gateway. This would be done via translation-rules/translation-profiles on the voice gateway itself.
Look for a translation profile that is using a translation rule for the "calling" party in your IOS config.
You could also check DNA on the CUCM to see if the calling party transform is occurring somewhere else.