Судя по всему, Вас смущает размер некластерного индекса, поскольку кластерный индекс содержит сами данные. Может быть, удастся сделать кластерный индекс покрывающим и те поля, которые используются в не кластерном индексе.
С другой стороны, постоянное добавление и удаление записей неизбежно приведёт к сильной фрагментации страниц таблицы. Бороться с этим можно только переиндексацией. Я надеюсь, что у Вашей АТС есть такое время суток, когда акивность звонков не велика и можно запланировать переиндексацию на это время.
Ещё один вариант, это натравить на Вашу таблицу ITW, и посмотреть, что он порекомендует под реальной нагрузкой.

Одни мои знакомые, занимающиеся биллингом, решили эту проблему созданием новой таблицы на каждый день. Не красиво - но даёт результат.

RE: SergSuper
Мне показалось, что Sergey именно переиндекспции (для борьбы с фрагментацией) и не хотел. Если я правильно понял, данные удаляются за прошедшие периобы, т.е. хранится только определённый интервал времени (допустим неделю). Тогда, можно завести 7 таблиц, по дням недели, которые будут дропаться в нужное время - и никакой переиндексации....