My guess: Scatter does not scale the instances out of sight to 0, but actually deletes them. Therefore, the index of the instances is in constant motion and that is why as soon as it changes, the random color distribution changes.
I could only avoid the "jumping colors" by using a Cloner and an LOD object, because my "patented use the variation shader in Object name mode" even failed here ;)