There are 2^80 possible onion domains and only ~10,000 are currently used. Simply brute-forcing the entire namespace isn't effective, especially because the verification step is a web service that has to try and fetch an onion service descriptor to see if it's online.
Also, onion domains are Base32-encoded, which means that they aren't case sensitive and they don't use the digits 0, 1, 8, and 9.