They should just use SPF. This is what SPF is designed for, and it allows them to keep the user experience simple and straightforward. No weird passphrase to enter into the email, no weird random email address to email to, etc.
If your address is gmail and my address is gmail, our mx domain has the same spf record and same IPs. Sure, some mail servers will prevent you from authenticating with one ID and sending as another, but many others will let that slide.
Gmail won't. Hotmail won't. Yahoo won't. In fact I can't think of a single authenticating mail service that doesn't also validate authorization (e.g. you can only send as you).
Now maybe you're going to point out micro-mail servers, but that's kind of beside the point because very few other people share it with you. e.g. you used gmail as your example, but services like gmail aren't vulnerable to that.