Is the problem over the direct PSTN connection or the VoIP one? Is the PSTN connection analogue or digital. Can you confirm that the caller ID in question is the one seen by PSTN callees? How are you specifying the caller ID to be sent? Can you confirm that you are trying to force a particular value, indepent of that for the incoming call?
If the problem is over an analogue PSTN connection, Asterisk cannot send caller ID over such connections, so this is comletely in the hands of the PSTN provider.
If the problem is over a VoIP connection, do you use fromuser? This normally overrides any callerID that may be provided elsewhere, although sendrpid may get round this?
Can you confirm that have registered the caller ID that you want sent with the the service provider over which you are, unsuccessfully, trying to send it?