In quantum mechanics, however, we have Block wavefunctions with lock-step periodicity that extends throughout the crystal. There seems to be no scattering of our Block states by the periodic potential... instead the effect is simply to make E(k) a complicated function. Where is the classical analogy?
To gain some appreciation for what is happening, consider the motion of visible light through, say, a diamond crystal. Certainly the light is scattered by each electron and nucleus that makes up the lattice, but we see straightforward behavior. The effect of all of this scattering is present but seems to produce only a minor change: a non-unit the index of refraction. Of course, if we use light with shorter wavelength (say X-rays) we begin to see Bragg scattering from the lattice. Similarly for electron waves: for small k where the wavelength is large compared to the lattice spacing, we see straightforward behavior (that nevertheless is the result of multiple scattering). However, when the wavelength of the light is comparable to the size of the lattice (e.g., near the first zone boundary) we see major effects: band gaps=non-propagation of waves that satisfy the Bragg condition.
Of course, Ehrenfest's theorem is still correct: if we localize a probability blob to say, 1/10 of a lattice spacing (which will require highly excited electron states), that blob of probability will follow the classical trajectory. The indefinite initial position and velocity (as required by Heisenberg's uncertainty) means varying initial conditions. Classically such different initial conditions result in divergent trajectories. Expect the probability blob to "quickly" spread out.