Thanks for the explanation. Indulge my offtopicness for a second. As I've been a database developer (Among a million other projects) for a while now(13+ years), might I offer a suggestion for the future?
Add a 1 bit boolean(Yes/No) display flag to the record layout.
The security layer allows who can view and or set the field in the table. When the range of records is displayed after a query, the "Viewable" field is simply a parameter on the SQL. Whatever parses the final output can add in "record xx removed by moderator" for all us normal schlubs where the Sequence(post) number has a gap. Admins and such can change the flag or just be allowed to view the deletes.
What's the end result? No more oddball changes in the index, causing the database to be-reindexed. It would behave just as fast as it normally does.
I ran into a similar problem on one of the commercial medical databases we had that was removing lots of records because they were superceded. We were removing them into a history table, indexing the database and refreshing the works. It wasn't a problem till we hit about 20 Million records. After the re-design, the purging was a monthly maintenance thing that queried all the "non-view" flags, moved the records into an "After 1 month" history table, deleted them from the frequently accessed table and re-indexed the table once.(I didn't design the DB from the start, I was brought in to fix it, so don't bark at me for a crappy design to begin with:) ).