List of steps to reproduce (step by step, including full links if applicable):
What happens?:
The page is missing from Special:NewPages
What should have happened instead?:
The page should be added back to Special:NewPages
Software version (if not a Wikimedia wiki), browser information, screenshots, other information, etc:
1.35.3
I vaguely recall this being intentional as NewPages seems to be aimed at content curation, and experienced users like patrollers and administrators that can perform (un)deletions would not be subject to such review, and the deleted page may have likely undergone review before.
Having said that, I'm not entirely sure of this or whether it is something worth revisiting or in need of clearer documentation and/or expectationg setting, so I'll leave this own for the owners to triage.
As of writing, the Page-deletion component is lacking an owner. But, I'll tag Recent-changes since Special:NewPages kinda falls under that and does have an owner that may be able to offer some thoughts.
@Porplemontage -- thank you for filing this. It seems to us that this has been the behavior for a long time, and is potentially even intentional (as @Krinkle said). Have you heard from others that this is an issue that needs to be changed? If not, I think we'd be inclined to leave it open but not take action yet, and wait to hear if other people agree.
I think this is a duplicate of T26203: Undeleted pages should be added to new pages.
T26203#5669239 explains why this happens.