This is definitely one of our hard problems. There are some optimizations -- e-tags / last modified headers, comparing page content hashes -- but there's also only so much you can do before you just have to check the page again.

Last modified headers is always set to the current time in the majority of cases, and it also requires a web request too (albeit a HEAD request would likely suffice)