I'm not aware of any mail providers that require DNSSEC. Were you thinking of DKIM? That's just 1 more TXT record (to publish the public key used to verify the signature), and some mail signing software if your mail server doesn't have that feature built-in (which is freely available).
...Or are they, except not in cash? :) Jokes aside, that's a fair observation, but then one should be able to "transfer" their address by paying a one-time fee, rather than getting a GSuite subscription.
The nice thing about a law is we can figure out how to do it after, not before. :)
It wouldn't be difficult! There are 7.6 billion people on the planet, an average email address is probably 25 characters. If every email address is forwarded, that's ~380GB of forwarding data (from address + to address) - and keep in mind that's the stupidest implementation and the worst case possible. I'd like to think that someone who offers a public email service can reserve 380GB of SSD for a forwarding table without going out of business.
Practically, I'd expect vendors to quickly agree on a "301 permanently moved" scheme. So if a Yahoo user is sending an email to a GMail user who moved to a private mail server, Yahoo wouldn't even bother pinging GMail (after the first time) because they'd know that address was moved.