Vielleicht probieren sie mittlerweile auch Wortlisten und Kombinationen bei den großen TLDs durch. Das würde ich jedenfalls diversen Akteuren, die Domainlisten verkaufen, durchaus zutrauen. Für eine grundlegende Prüfung reicht es ja DNS abzufragen, was vergleichsweise extrem kostengünstig ist und durch die Nutzung von verschiedenen Resolvern sehr gut verschleiert werden kann. 
Infiltrierte Browsererweiterungen sind Gerüchten zufolge auch eine nette Möglichkeit, um Domains zu sammeln, die nicht öffentlich auftauchen. Kompromittierte Postfächer bei Kommunikationspartner verraten auch reine E-Mail-Domains. Vielleicht war die Domain auch schon einmal vor mehreren Jahren registriert und aktiv. Es gibt so viele Möglichkeiten, wie Domains bekannt werden.
Ich bezweifle jedenfalls, dass die Versender von solchen Phishing-Kampagnen die Domainlisten selbst zusammentragen. Die kaufen die grundlegend bestimmt ein und filtern sie maximal anhand der A/AAAA-Records. Wobei es mich nicht wundern würde, wenn man die auch schon fix für ein ASN einkaufen kann. Dann haben die Phishing-Versender nur noch den Aufwand, das Zeug über fremde Server oder Postfächer zu verschicken.