I did this while working on a project for network solutions. I'ts been a few years, but I'm pretty sure we used whois to figure it out.
For instance, this is the output from an available domain:
[me@comp dir]$ whois etreeeee.com
[whois.crsnic.net]
Whois Server Version 1.3
Domain names in the .com and .net domains can now be registered
with many different competing registrars. Go to http://www.internic.net
for detailed information.
No match for "ETREEEEE.COM".
Last update of whois database: Thu, 1 May 2003 06:00:35 EDT <<<
plus a lot of other junk.
This is an unavailable domain match:
[me@comp dir]$ whois etree.com
[whois.crsnic.net]
Whois Server Version 1.3
Domain names in the .com and .net domains can now be registered
with many different competing registrars. Go to http://www.internic.net
for detailed information.
Domain Name: ETREE.COM
Registrar: NETWORK SOLUTIONS, INC.
Whois Server: whois.networksolutions.com
So all you need to do is something similar to
$res = strstr(whois $somedomain, "No match for \"$somedomain\"");