If you’re on Mac, you can open the Terminal and type in:
whois exampledomain.com
…to get at the owner and whois record. Note that many times, you won’t get the real owner’s contact information. Hosts like Dreamhost, for instance, provide a means for their registrants to circumvent personal whois records, so it can be tricky sometimes.
Another thing to look out for, and this is nothing I can confirm to be 100% accurate, is that there might be a risk, using “free domain lookup” services out there, in that they can (potentially) hijack your domain name query and register them before your eyes. (Note, again, this has to be confirmed by someone in better knowledge, but at least this is what I have been suspecting for a while, as well as having also experienced once—be it true or not).
Finally, I use somewhat of a hack to get multiple results on domain name availability from this source:
http://search.domaininfo.com/search.asp?selc=0&domain=websitename&tld=se,com,net,org,info,biz,nu,it,in,eu&submit1=
You may edit the above address to include more or less top-level domains (TLDs). And I also recommend using any of the various browser tools for performing custom searches, by typing a shortcut letter in the address bar, followed by a search term, for quick searches.
In my case, I’m using Safari and the Safari plugin called Glims, and I’ve set it up so I can simply type:
U sitename
…to quickly retrieve a list of free/occupied domains from the aforementioned source. (U being short for URL, but you may of course pick any other letter as well.)
As for a method of negotiating domain buy-offs, you might want to take a look at Sedo or Escrow.com. I haven’t ever tried them myself, though.