Índices não-clusterizados ficam fragmentados sempre que as divisões de página ocorrem; isso acontece principalmente ao inserir dados não sequenciais, ou seja, não na ordem de índice (acontece ocasionalmente ao inserir na ordem de índice também - mas não com tanta frequência).
Considere reconstruí-los com 50% de preenchimento, ou seja, todas as páginas atuais ficarão meio vazias.
Isso fornece o tempo necessário para dobrar o índice antes que a fragmentação se torne um problema novamente.