This is what I tried, and it seems to work (cannot really test all possibilities, though):
I set context=from-pstn-toheader-telekom in my incoming trunk configuration, and added this to extensions_custom.conf:
[from-pstn-toheader-telekom]
exten => _.,1,NoOp(Attempting to extract DID from Telekom SIP To header)
exten => _.,n,gotoif($["${CHANNEL(channeltype)}"="SIP"]?SIP)
exten => _.,n,gotoif($["${CHANNEL(channeltype)}"="PJSIP"]?PJSIP)
exten => _.,n,NoOp(Unable to determine SIP channel type)
exten => _.,n,goto(from-pstn,${EXTEN},1))
exten => _.,n(SIP),Goto(from-pstn-toheader-sip,${CUT(CUT(SIP_HEADER(To),@,1),:,2)},1)
exten => _.,n(PJSIP),Goto(from-pstn,${CUT(CUT(PJSIP_HEADER(read,To),@,1),:,2)},1)
[from-pstn-toheader-sip]
exten => _00Z.,1,NoOp(Replace 00 to + in Telekom SIP To header)
exten => _00Z.,n,Goto(from-pstn,+${EXTEN:2},1)
exten => _0Z.,1,NoOp(Replace 0 to +49 in Telekom SIP To header)
exten => _0Z.,n,Goto(from-pstn,+49${EXTEN:1},1)
exten => _Z.,1,NoOp(Replace X to +496251X in Telekom SIP To header)
exten => _Z.,n,Goto(from-pstn,+496251${EXTEN},1)
exten => _.,1,NoOp(Replace in Telekom SIP To header fallthrough)
exten => _.,n,Goto(from-pstn,${EXTEN},1)
Do you see any major flaws in this?