Hi Daniel
this is a common scenario and the UAC (the phone) should be able to cope with it.
By parallel forking, there will be two different To-tags, so practically during the call setup, the UAC has to maintain two different (early-state) dialogs, when one is answered with 200ok, the other one is cancelled.
If the UAC that you use doesn't support parallel forking by downstream proxies, then either you replace it with a capable one; configure it with a single codec; as you suggested, strip codecs on proxy leaving a single option; or route first via a transcoding system.
The UAC in question, is the Swisscom Mobile Network.
I guess it's not feasible to tell Swisscom to replace all the millions of mobile phones in operation. :-)
They tell me it's in the RFC, you side is not RFC compliant.
Mit freundlichen Grüssen
-Benoît Panizzon-