とりあえずindex領域を、専用の物理媒体に分けて置いてみたら？
削除->更新->再作成は、オンライントランザクションがないと
保証された時間帯にやるならいいけど、
だれかが繋いでるかもしれないときにやるのは馬鹿。

あと、本当にそのインデックスが有効に使われているかどうか
調べて、それほど処理に貢献していないようなら消しちゃうのも手だぞ。