Ну выше человек правильно написал. У вас вариантов то особо и нет. Либо долбить своего оператора и просить подмену CID, либо менять оператора. :) Технически ваш оператор это может сделать, просто видимо не хочет. Если рассуждать юридически, то да, вероятно это несколько "серая" схема, но многие идут на уступки клиентам.
Не сочтите за рекламу, но мы с недавнего времени берем транк на 4 линнии у new-tel.net, с 499 номером обходится всего в 950 рублей в мес., что тоже недорого. По запросу они согласились подставлять другой CID (другой наш номер в коде 495) при исходящих вызовах. А для входящих на нашем 495 стоит безуслованя переадресация на их 499. Пользуемся неделю, полет нормальный. Единственный косяк с CallerID при входящих, обрезают зачем-то префикс 8 у российских номеров, обещали исправиться в ближайшее время. :)