You could request people to home sub-domains or even register full domains for you and populate MX records etc. You simply have to test the domain records before sending. You could periodically generate a TXT record, say annually, that should be updated.

I already support several projects like this.