В большинстве случаев проблемы с Early Media связаны с нестыковкой между PRI и SIP, по большей части на стороне именно SIP. Именно для этого ТС и стоит изучить соотвествующую статью на voip-info.org
С точки зрения PRI - там всё просто, нужно просто сравнить сообщения во входящем и исходящем звонках и добиться похожести.
Насчет регионов - бывает и это, хотя и редко. Чаще - лажа в параметрах pridialplan / prilocaldialplan, неумение пользоваться Progress() в диалплане.