asterisk users - Feb 2009 - set caller id on outgoing calls through BRI ISDN lines

I'm trying to set caller ids on outgoing calls.
I have a quad BRI B410P card connected to my telephony provider.
I know the list of DID numbers the provider assigned to my company.

If I don't set the caller id then the callee always sees the same
"top-level" number.

If I set the caller id to a specific DID number we own, the callee keeps seeing
the "top-level" number, as though the CALLERID function had no effect.

When dialing out on the BRI lines I see this in *CLI: 

    -- Executing Set("SIP/4053-b2ba5a28", "CALLERID(all)="My
Name" <9999999999>") in new stack

where 9999999999 is a valid DID number.

My telephony provider swears that if the BRI lines are connected to our PBX then
we can set whichever caller id we want.

How can I be sure that they are right?
What can I do to see if Asterisk is failing to set the caller id and why?

An misdn debug doesn't seem to reveal any errors setting the caller id:

P[ 0]  --> Group Call group: ISDN_GROUP
P[ 1] Group [ISDN_GROUP] Port [1]
P[ 1] portup:1
P[ 0]  --> * NEW CHANNEL dad:656660499 oad:(null)
P[ 1] * Queuing chan 0xf651398
P[ 1] read_config: Getting Config
P[ 1] config_jb: Called
P[ 1]  --> * CallGrp: PickupGrp:
P[ 1]  --> TON: Unknown
P[ 1]  --> LTON: Unknown
P[ 1]  --> CTON: Unknown
P[ 1] * CALL: g:ISDN_GROUP/6666666666
P[ 1]  --> * dad:6666666666 tech:mISDN/1-u23701 ctx:from-pstn-deviate-custom
P[ 1]  --> * adding2newbc ext 6666666666
P[ 1]  --> * adding2newbc callerid 9999999999
P[ 1]  --> pres: -1 screen: -1
P[ 1]  --> pres: 0
P[ 1]  --> PRES: Allowed (0x0)
P[ 1]  --> SCREEN: Unscreened (0x0)
P[ 1] NO OPTS GIVEN
P[ 1] I SEND:SETUP oad:9999999999 dad:6666666666 pid:2626
P[ 1]  --> bc_state:BCHAN_CLEANED
P[ 1]  --> channel:0 mode:TE cause:16 ocause:16 rad: cad:
P[ 1]  --> info_dad: onumplan:0 dnumplan:0 rnumplan:0 cpnnumplan:0
P[ 1]  --> caps:Speech pi:0 keypad: sending_complete:0
P[ 1]  --> screen:0 --> pres:0
P[ 1]  --> addr:0 l3id:95bfc b_stid:0 layer_id:50010180
P[ 1]  --> facility:FAC_NONE out_facility:FAC_NONE
P[ 1]  --> urate:0 rate:16 mode:0 user1:0
P[ 1]  --> bc:8212590 h:0 sh:0
P[ 1] find_free_chan: req_chan:0
P[ 1]  --> found chan: 1
P[ 1] set_chan_in_stack: 1
P[ 1]  -->  found channel: 1
P[ 1] --> new_l3id 95bfd
P[ 1]  --> * SEND: State Dialing pid:2626
    -- Called g:ISDN_GROUP/6666666666
P[ 1] Sending msg, prim:30580 addr:41000104 dinfo:95bfd
P[ 1] handle_frm: frm->addr:42000103 frm->prim:30282
P[ 1] set_channel: bc->channel:1 channel:1
P[ 1] $$$ Setting up bc with stid :10010100
P[ 1] setup_bc: with dsp
P[ 1]  --> Channel is 1
P[ 1]  --> TRANSPARENT Mode
P[ 1] $$$ Bchan Activated addr 50010102
P[ 1] BC_STATE_CHANGE: l3id:95bfd from:BCHAN_CLEANED to:BCHAN_ACTIVATED
P[ 1] lib Got Prim: Addr 42000103 prim 30282 dinfo 95bfd
P[ 1] I IND :PROCEEDING oad:9999999999 dad:6666666666 pid:2626 state:CALLING
P[ 1]  --> channel:1 mode:TE cause:16 ocause:16 rad: cad:
P[ 1]  --> info_dad: onumplan:0 dnumplan:0 rnumplan:0 cpnnumplan:0
P[ 1]  --> caps:Speech pi:0 keypad: sending_complete:0
P[ 1]  --> screen:0 --> pres:0
P[ 1]  --> addr:50010102 l3id:95bfd b_stid:10010100 layer_id:50010180
P[ 1]  --> facility:FAC_NONE out_facility:FAC_NONE
P[ 1]  --> urate:0 rate:16 mode:0 user1:0
P[ 1]  --> bc:8212590 h:0 sh:0
P[ 1]  --> bc_state:BCHAN_ACTIVATED
P[ 1] Freeing Msg on prim:30282
    -- mISDN/1-u23701 is proceeding passing it to SIP/4053-b23d5580

The callee 6666666666 is expecting to see our DID 9999999999 on his/her phone
screen but is seeing our "top-level" number, say, 0000000000.

Help appreciated.

Vieri