Instead, I time <iframe>s, which allows SOP violations to be trapped the moment the browser barely starts thinking about rendering the target page. The other benefit is that <iframe> requests can be aborted quite easily when they are taking long enough for us to suspect cache miss - before the request is completed and cached.
The results should not be fuzzy, although the PoC uses hardcoded timings instead of doing calibration, which makes it a bit tricky with "outlier" clients (very fast or very slow).
I made some minor tweaks today, and the success rate should be greatly improved; there's now a mini-survey on the page, looks like ~90% of the people who bother to complete it are getting accurate results.
Better yet, do this for each target URL. Knowing the time that a miss takes vs. a hit will greatly increase your accuracy.
Also, does this work for Google+ (I don't have an account)? I'd be surprised if it did, since it uses X-Frame-Options.
To test if a user has recently visited Facebook, see how long it takes for the Facebook logo to load when called from your own page. If it's relatively fast, you can assume the image has been cached by the user's browser ... meaning the user has recently visited Facebook. If it's relatively slow, you can assume no cached version of the logo is available, so the user probably hasn't visited Facebook recently.
Results are fuzzy because "relatively fast" and "relatively slow" are not precise.