If the MediaWiki Page ID changes in the deletion+restoration process (I don't know if it does), then the PPID should be linked to the new ID. This might already work, but we need to verify it, add an integration test, and potentially fix it.
Somewhat related: