Hello @Martin,
Because plugins have a direct relationship to their placeholders, I would rather not move these automatically every time the user changes a page's template.
This can cause sync problems, as well as other data corruptions.
That said, when a template changes, the placeholders that are no longer in the template still remain in the database, the cms does not delete them (by design).
We can leverage this to create an "archived" placeholders section in structure mode which can be enabled/disabled (to avoid showing them all the time), and all this would do is fetch the placeholders
from the database instead of from the template, then just render the structure markup for the ones that are in db but not present in template.