There seems to be an issue with how the "Link Validation" scheduled job defines what is a broken link.
How to reproduce:
The "link" to the deleted page is now reported as broken. Which is a bit confusing because if you go to the page with the contentarea everything looks good, no broken references.
If the editor e.g. re-order the pages in the content area (actually just need to move it to the same place), and then re-run the link validation tool, there is no "broken" link anymore.
Nor really sure how it should work, but the current way is not very good :-). We have a client that have hundreds of these "broken" links in the Link status report.