A unique index on email, and a soft delete that leaves the row in place, which means an address can never be reused.
-- the problem
UNIQUE KEY uq_email (email)
-- a deleted user still occupies their address
-- the fix that works in MySQL, because NULL is not equal
-- to NULL for uniqueness purposes
ALTER TABLE users
DROP INDEX uq_email,
ADD COLUMN deleted_marker BIGINT GENERATED ALWAYS AS
(IF(deleted_at IS NULL, NULL, id)) STORED,
ADD UNIQUE KEY uq_email_live (email, deleted_marker);
The generated column is null for live rows and unique per deleted row, so live addresses are unique and deleted ones never collide. A partial index would say this more directly and MySQL does not have them. The alternative worth considering first is not soft-deleting at all — moving the row to an archive table keeps the constraint simple and is more work in exactly one place.