I'd say fight with your service provider...I've heard of them restricting what numbers you can present on redirected calls, but never that they outright reject them.
Is it because they use the same parameter like PAI for both CPN and authentication of the caller - so if CPN is not a number that lives on your SIP trunk, they reject the call?