Hola:
Mejor que php puro, y javascript (que para que sea puro debería cargar con antelación todos los nombres existentes, o triquiñuelas impensables), podrías hacer una petición Ajax, que justamente obtenga ese mysql_num_rows de la búsqueda php/mysql... claro está que un valor cero equivaldría a disponibilidad.
Saludos
