Ideally you would sync up codec usage, so the third party switch board would use G729 when going to call across the trunk to your SIP provider.
Region settings in CUCM typically dictated codec usage. Does your SIP provider talk straight into your CUCM or have you a CUBE in the path?
also can you provide the CUCM traces of such a failed call.
also are your XCODE resources registered in CUCM?
Please remember to rate useful posts, by clicking on the stars below.