Just a couple of thoughts to add:-

1. No-one has added some maintenance tasks that you didn't know about, have they? Perhaps an ill-advised statistics rebuild just before your index rebuild runs?

2. Is your storage SSD based? It's becoming clear that such devices require periodic maintenance to prevent their performance from dropping off.