This sounds like a multi-tenant application, and we already know that MT apps are exceedingly hard to do and do not scale well with FreePBX. This outbound CID stuff is probably one of the most challenging areas when you have just voice - adding FAX to the mix certainly doesn't make it easier.
I'm going to admit a little ignorance on this, in that my setups have always used separate FAX extensions as the source for the outbound FAX. I've always used mail2fax scripts for my outbound faxing and have never tried to send a FAX from UCP. In spite of that, I assume that the semantics for that connection are only somewhat different than normal Faxing.
The Caller ID set for voice calls from the extensions should all be working correctly so you should be able to do one of the following to extend your current system:
Set the CID entry on the extension as you want it set and honor that set CID on the outbound route and trunk. In other words, allow any outbound CID and do not override the CID on the outbound route and trunk. In my setups, I always set the Caller ID on the FAX extension, so this works for my systems.
Use the "extension" field in the outbound route (FPBX 13+) to override the extension Caller ID and to choose a different outbound trunk (perhaps). The advantage of this approach is that, if you have different extensions that you want to be associated with very specific extensions (to support multi-tenant, for example), you can control the outbound semantics at the Outbound Route level (thereby limiting the outbound routes for your callers).
The extension "extension" to the outbound route provides a new semantic for routing calls that prefixes used to facilitate. Now, by querying the extension, you can control the outbound call without having to use prefixes. You may be able to use this feature to control your FAX CID.
Another (more involved) approach might be to use a custom outbound context to route the calls based on their source. Once again, this is theoretical for me since I don't actually have an application for anything like this, but the approach would be to look at the parameters of the call (FAX from UCP, for example) and set the extension or add a prefix (for example) based on something in the outbound calls setup data. This way, you can select the specific outbound route to override the CID to match the one you want. Note that you could also set the Caller ID in a custom outbound context and just send the call out on it's merry way.