There's nothing "complex" about any of this... they just go looking for subdomains that were CNAME'd one upon a time to domains which are now abandoned (eg. marthastewart.msn.com -> msnmarthastewartsweeps.com). So they register the domain, set its DNS records, and then can verify SMTP as the subdomain as well.
There's no DNS vulnerability or anything, just large organizations with subdomains slipping through the cracks. It will take a while to be resolved too because we're probably talking hundreds of records in each case that need to be checked manually.