My guess is that they ran selective search on the domains which get registered with any registrar, thats the trigger to start the search. .gov domains are not managed by your typical registrar which is selling the domain registration information to all these downstream partners/scavengers (for lack of better word)
The OP says it's using CT logs, not new domain registrations. The approach you have in mind would not include subdomains and would be less likely to coincide with a new server being configured.
Yes CT is explicitly stated source which is why I qualified it with "Guess" for domain registration. There were couple reasons for that -
1. Quite a few websites in the search results where just on HTTP
2. The .gov sites do use public certificate authorities like digicert, verisign, amazon & letencrypt so they would have been captured unless they are removed explicitly
And yes the domain registration would not include subdomains