Some termination providers do not accept a toll free number as a caller ID becuase they cannot properly rate (determine origin). If the number is not accepted, some ternination providers will fill the caller ID with any number since it will save them money in the long run.
If this continues and you have verified the Outbound CLI mapping is set, create a ticket in the Help Desk and we may be able to change the route.