Долго бился с их техподдержкой, в итоге на форуме (не в СТП :) подсказали таки, что их софтсвич не любит Delayed media, который цисковые шлюзы используют по умолчанию в случае проброса IP-IP звонков.
Копание в документации показало, что как раз в том момент вышел софт 12.4(20)T1 в котором добавили такую фичу — Forced Early Media на IP-IP звонках.
Скачал свежий софт, привел конфиг примерно вот к такому виду:
voice service voip redirect ip2ip sip early-offer forced
и все побежало. :)
Почему в топике написано «провайдерами»: в последующем я столкнулся с точно такой же проблемой при стыковке с Huawei SoftX3000.
Также, есть подозрение что аналогичная ситуация с Мерой.