This need not be an automatic action, though; you might choose to postpone the migration, and offer a separate tool for the user to run.
This prevents any packages from depending on such a package, though: they can no longer be automatically installed, because their dependency cannot, too.
This changes the concept of package management seriously enough.