Cuando hagas la consulta puedes publicar un mensaje por defecto que indique solamente algo como "Data no encontrada" y luego haces una comparación en el código de AJAX.  Algo así
   
Código PHP:
Ver originalajax.onreadystatechange=function(){  
    if (ajax.readyState==4){
        if(ajax.responseText != 'Data no encontrada'){
            var respuesta=ajax.responseXML;  
            campo1.value=respuesta.getElementsByTagName("nombre")[0].childNodes[0].data;  
            campo2.value=respuesta.getElementsByTagName("apellido")[0].childNodes[0].data;  
        }else{
            alert('Data no encontrada');
        }
    }  
}