Sounds like the two proposed new metadata tags are "Previous AFD" and "Previous Draft"

I'm guessing when the page is added to pagetriage_page, it does a one time check of the logs to see if the page has been deleted. If so, it then creates a "previously deleted" metadata tag.

That would be a good time to do other kinds of checks, such as the checks for our two new tags. The tags themselves would need to be added to pagetriage_tags. The data for each page is stored in pagetriage_page_tags

Would also need code to filter by these tags, display these tags in Special:NewPagesFeed, and display these tags in the Page Curation toolbar's information menu.

I mentioned this off-wiki to Novem, yep.

One more scenario I run into frequently (outside of draftifications, which NL mentioned) is seeing the "Previously deleted" tag next to a page (often a BLP) which was CSD/PROD'd 10+ years ago, usually with a different subject, despite having the same name, so the previous deletion really has no bearing on the current iteration of the page.

In T313650#8135537, @Giraffer wrote:

One more scenario I run into frequently (outside of draftifications, which NL mentioned) is seeing the "Previously deleted" tag next to a page (often a BLP) which was CSD/PROD'd 10+ years ago, usually with a different subject, despite having the same name, so the previous deletion really has no bearing on the current iteration of the page.

Not always easy to discern the nature of the previous instance and determine its relevance to the present article. This is where a scratchpad of inconclusive review findings would be useful: I sometimes add the Old Prod / Prev Afd template to the new instance, and where appropriate add a note about it probably not being the same person. Maybe an additional template for placing structured investigative findings onto the new article's Talk page could be useful, and then could in time be consumed as structured information?

A direct link to the AfD/Draft in question would also be useful.