Going to link this to Umbraco V17 - URLs are generated in the backoffice but not persisted to umbracoDocumentUrl as I believe there is good probability of these being related.
I did not want to fill out any issue in the tracker, as the fantastic @justin-nevitech suggests above, because “something bad happens occasionally, with zero noticeable patterns or reproduction steps” is as much as i could fill out and that doesn’t strike me as productive but the linked thread actually does have some good discovery work behind it.
Hopefully linking these two provides the spark to get a productive starting point in place to diagnose the routing issues. It sounds like there are a number of different paths that people are running into the issue - so a common spot like DocumentUrlService does seem like a common point that could be at the heart of this mystery.