The match threshold has a minimum of 0.1. Are you using tags and categories on the site? Are those being considered? You can check under the relatedness options, which you can show from the Screen Options.
Are you seeing related posts under the “related posts” meta box in the edit screen?
This sounds like it might be a systemic issue and I’d love to see this resolved. Thanks for reporting it.