Alterations to the validation code, together with the non-crawing of links on non-validated pages have made the first graph of a url highly unpredictable e.g. returning only a few results or even unvalidated links in strict mode.
Subsequent requests made once the graph has been built always return exactly the same data i.e. the correct data.