How do WordPress permalinks work?

I am not sure on your terminology there (“plan” vs “post type” permalinks bit).

In general the rules are generated and persistently saved when you change anything in Permalink Settings. Or something else like plugin initiates the process.

When you change settings you “previous” state ceases to exist, rules are generated for the current and current only.

However there is a fair bit of “magic” in redirect_canonical() monstrosity of a function that tries to “fix” links that don’t look quite right, but might be close enough to make sense of. It sort of works here and there, but not something you should rely on.

In a nutshell if you want to switch between two different pretty permalink configurations you would likely need to take care of redirects manually to have old links work reliably.

If you are just going from non-pretty to pretty permalinks that is much easier and handled magically.