So I upgraded to YARPP v3.5.1 a few days ago. Ever since, my new posts come up with "No related post".
It's worth noting that I have W3TC.
The workaround is to either modify the threshold to force the plugin to flush the cache, or install the "experiment" plugin to flush it manually (not sure why this feature doesn't come with the official plugin). Once the cache has been built (it really takes a few tries, as it tends to stop prematurely), I have to clear the cache of W3TC to make the related posts appear on the aforementioned new post.
Is there a fix for all this?