See https://www.mediawiki.org/wiki/Topic:U9njvte6e2wjuqx5 for context.
See https://xtools.wmflabs.org/pages/en.wikipedia.org/DrVogel. Here redirects are not supposed to be shown. The two pages that were deleted were redirects.
We hopefully can efficiently detect if a deleted page was a redirect. If it was, that shouldn't be included in the results, and in this case, only the recreations of those pages (also by DrVogel) should be shown.
There is no formal log of redirect creation/removal, but there are tags (mw-new-redirect). What we could do is check if the initial deleted revision was tagged as a redirect, and check subsequent deleted revisions to ensure the redirect wasn't removed (which will also be tagged). If the deleted version stayed a redirect throughout it's life, that means we shouldn't count it as a deleted page (since in this example we've chosen not include data on redirects). These tags were introduced only recently, so historical data will still suffer from this problem. I also question if this approach will be performant enough, but we could at least do some experimenting.