>The advice I've seen is to not search for the domain first, just register it outright from the start. The domain registration business is run with all of the integrity and customer focus of TicketMaster.
What if you don't want to cough up $10-$20 on a whim? Would doing a whois (using the NIC's whois site) suffice?