Die Idee mit dem Vorausfüllen ist gut. Mich würde nur der Aufwand abschrecken und der Overhead, der dadurch entsteht.
Ein REORGANIZE müsstest du nicht nach jedem Löschen ausführen. Ich schätze mal, dass 1x am Tag genügt. REORGANIZE ist Standard-MS-
SQL, das kann schon mehrfach aufrufen.
Vielleicht kann man auch Hardwareseitig optimieren: Mehr
RAM + den Index auf eine eigene SSD.