At least one case where rebuilding indexes helps…
We found that after deleting 250 million “lower” rows from a table with a monotonically increasing sequence, our MIN range scans were incredibly slow. Richard Foote describes this much more clearly than I can this morning, so all this post will be is a link to his blog about it.
Enjoy…
http://richardfoote.wordpress.com/2008/07/01/deleted-index-entries-part-v-trouble/