Pues hombre he revisado el sitio web del registrador oficial de .com.co y CO y el whois de ellos puedes implementarlo de forma sencilla con ajax, ma imagino que MaxWhois tiene un archivo de configuración donde agregais la url de verificación del whois y la palabra o frase que indica si el dominio se encuentra registrado, la url es la siguiente
http://whois.co/co/whois-co.cgi?TLD=...co&TYPE=DOMAIN
Si el dominio no está registrado devolverá
Cita: There were no records matching your WHOIS query.