Whilst some matches do have trees few if any of the UK trees go back very far, grandparents seem to be the norm with my matches and I generally struggle to find bmd records to support the claims in the trees.
If they have minimal trees on MY I will search for the dead-end in Ancestry trees, which is very quick and easy to work with in going back more generations. Most people born before 1900 occur in a tree, and many up to the 1940s.
I've been able to identify far more links with matches from quickly piecing together trees. Typically takes no more than 10 minutes per match. Even some where the link goes back to the 1700s and they just listed their grandparents in their tree.
On Ancestry, there is a search button at the top right of profiles:
Next to the clock and help icon.
If they have a short tree (on Ancestry) pull up all the dead end ancestor profiles, press the search button and look for continuations of the line in public trees.
For MyHeritage, you'll need to type them in.
Using this, I have been able to identify the link for about 80% of my matches over 40cM where I can identify the test taker.
When I can't find the link I assume it's due to a birth out of wedlock or infidelity. The historic infidelity rate was 1.35% or 1% according to two studies, throw in births out of wedlock and we're at about 3 if not 4% for the period in which autosomal tests are useful. Going back to 5th cousins, that's 11 pairings, so somewhere in the region of 1/3 chance of a non-paternal event.