This pretty much highlights a general problem of groups: If the distribution groups for the email client are managed independently from the certificate groups then there will inevitably be discrepancies. The obvious solution is the usage of groups managed by a central service for email addresses and certificates. (Or an encrypted mailing list service.)

a) is a good idea.
b) is already covered by T6240: Kleopatra: Add column for groups in the certificate view.

Tested with Version 3.2.2.2405000+git~ (Gpg4win-4.3.2-beta41)

This works in principle, for for single certificate deletion as well as multiple, the warning comes up with appropriate wording iff all certificates where in that group.
So I'll close the ticket for now and plan to open a new one with a low priority.

Points for the future ticket:
When only part of the selected certificates is in a group, all are shown, anyway:

Here one of the certificates was not in the only existing group.

Here the wording is technically correct, but confusing in the case of a revoked certificate where no encryption will happen anyway.