One problem with subdomains is combinations. The number of records can multiply rapidly if we get into additional levels of hosting or redirection domains.
Another problem is how to automatically distinguish an actual hosting subdomain or redirection site from a wildcarded DNS Address record:
my.pretty.fluffy.bunny.freehostingprovider.com
vs
random.or.keyed.gibberish.here.spamyisp.biz
It's not clear how these can be programatically distinguished.
Finally, it seems unlikely that these subdomain hosting or redirection sites would be major sources of spam; more like occasional, minor annoyances. There is a disincentive for a hosting or even redirection provider to host a spam site due to excessive traffic, complaints, retaliation, blocking, etc. Most providers in general tend to be mostly whitehat or mostly blackhat.
Most of the hard core spammers are already settled at the blackhat or clueless providers in China, Korea, Brazil, etc. A few professional spammers are probably responsible for most of the spam and are more important to focus on than the minor clueless abuser whose free site on a mostly legitimate provider is about to get shut down.
Jeff C.