I believe this will only work if you're using a Digital Line Card and have a T1 or PRI for your phone service.
In that case you use the dial plan pretanslator named "Outbound Caller ID Presentation."
This is easier if you can separate your extensions and theirs (for example 100s for your company, 200s for their). Then you would tell the prestranslator to show your number when the call originates from 1xx extensions and their number when originated fro a 2xx extension.
As far as it showing the company name, I'm not sure if that relays through to the telco or not. I know letters can work over VTL lines between 2 NBXs, but the PRI may only accept digits.
If you're using analog lines as far as I know the NBX can't control the outbound ID -it's set by the line provider.