I ran shell scripts on 10 nodes with fast backbone connections, making DNS queries of all possible 4-letter and 5-letter .com's. Obviously, if the domain doesn't NXDOMAIN, it has been taken.
At the time (before domain squatting was shut down) all legal 4-letter domains were taken.
From the NXDOMAINs, I ran a much slower whois script to see if the domain was registered but missing a DNS entry.
From that final list of unclaimed domains, I was quickly able to spot the one I wanted.