Forse è dovuto a qualche cambiamento importante dell'algoritmo?
Ne dubito. Non vi è mai stata una forte corrispondenza tra i comportamenti della toolbar e gli algoritmi di Google.

Probabilmente hanno semplicemente cambiato idea ed hanno deciso che il grigio era più attinente ad una pagina non ancora indicizzata.