Can these services not use the same fallback mechanism that already exists for non-passkey logins? i.e. an email with a 1-time code or similar. Yes that somewhat defeats the purpose of passkeys but that option is going to exist for a long time regardless of passkey adoption.

If you don't want to downgrade security, how about requiring confirmation from another session that is already logged in using a passkey? e.g. You try to log in on PC2. A prompt appears with something like "confirm this login from [PC1, etc.]". You log in on PC1 using your passkey. The service recognizes that the login id definitely you, or at least someone in possession of your physical device and login method for that device. Therefore, it then allows PC2 to register a new passkey. Kinda similar to how google confirms new logins by sending a notification to your phone.

You generate another passkey is your answer. How do you do that? The exact same way you do today. Why would you need to delete invalid passkeys? You wouldn't.