Have you looked at the 3CX logs to see what is actually coming from your provider? I'm assuming that you are using a VoIP provider given that you are attempting to change outgoing CID.
Does you provider send name display, is the Authentication ID appearing where the name normally would?
What provider are you using? Perhaps others, using the same provider, have some "tweaks' to straighten this out.
You've mentioned that devices that receive the calls, but no details about the trunks.