I've had some success tracking historic address changes by hunting down old phone books in libraries.

Comparing phone books from different years, it appeared that every single family name suddenly moved to a different address on the same street. Doh! That would never happen.

Then a light bulb popped on over my head when I realized they must have renumbered all the addresses instead.