Comment by bobmcnamara

Use a hash chain!

Each time you resolve, the resulting IP can be part of the hash for predicting a future hostname.