Antes del onreadystatechange=function() debería estar el innerHTML que contiene el GIF y despues de todo va el responseText, mira este ejemplo:
Código:
document.getElementById('div').innerHTML = '<img src="images/sending.gif">';
ajax.open("POST", "web.php",true);
ajax.onreadystatechange=function(){
if (ajax.readyState==4) {
c.innerHTML = ajax.responseText
}
}