Yes, the trunk supplier has to support it and you have to set it up correctly in the PBX.
There are lots of places in the system that “manage” the Caller ID (CID). Any or all of them could be messing with your success.
The first step would be to call your SIP provider (most land-line carriers do not support foreign Caller ID and force the line to use the one for that line) and ask them if they support foreign Caller ID. If they do, the problem is in your system.
If they do not, I know of at least three providers (Alcazar Networks, VOIP Innovations, and SIPStation(IIRC) ) that all support the use of foreign Caller ID.
When you find out what the ITSP’s position on foreign caller ID is, we should be able to help you. Search for “foreign CID” in the Search icon for more information on this commonly discussed topic.