Si os sirve de algo a mi me paso con Driskol, usuario del foro y que se encarga de liberamimovil.com actualmente, y el problema no era del terminal, ni de quien lo intentaba liberar, sino del SAT.
En mi caso concreto tenía una Magic de Vodafone que tuve que enviar al SAT para un cambio de placa base tras un brick (y por tanto cambio de IMEI) y dicho IMEI tardó 1 mes en poder liberarse debido a que el SAT no se dio ninguna prisa en añadir ese IMEI a los IMEI en circulación.
Es posible que vuestro caso sea algo similar, tal vez al "darlo de alta" han introducido mal el IMEI y por ende al intentar liberarlo ese IMEI no aparece en ninguna parte, y por tanto no es liberable algo que "no consta como bloqueado" en ninguna parte.
Creo que lo único que se puede intentar es contactar con el fabricante y con la operadora y decirles lo que ocurre, ya que es más que probable que el problema lo hayan iniciado ellos, otra cosa es que con quien se contacte de por medio este suficiente informado en el tema como para poder hacer que dicha petición llegue a alguna parte.