Haber si entiendo bien, según los comentarios:
Caso1: cuando llamas marcando
(int) 00 + (país) 49 + (num abonado) 12 dígitos : SI sale la llamada
Entiendo que esto sale por Movistar.
Caso 2: cuando llamas marcando
(10584) + (int) 00 + (país) 49 + (num abonado) 12 dígitos : NO sale la llamada
Entiendo que esta llamada sale por otro operador de Voz(10584)
Entonces el problema no estaría en Movistar, si no en el Operador(que utiliza el prefijo10584) que no estaria ruteando o conversando bien con los terminadores para ese destino.
Podrias tratar de coordinar con el Operador(10584) para que puedas realizar las pruebas respectivas. Para que ellos puedan capturar tráfico en el momento que Ud. realice la llamada de prueba y ver si le llega al Operador el numero que estas enviando a través de su servicio.
Has intentado llamar desde un telefono cualquiera de otro lugar(tu casa por ejemplo) marcando al mismo destino con el prefijo 10584?
Por el lado de Asterisk no deberias tener problemas en marcar esa catidad de digitos, ademas segun tus comentarios se ve que Asterisk esta lanzando las llamadas hacia el operador.