Hola:
Otro paginador "ineficiente" con ajax... son casos absurdos, ya que plantean eficiencia al no recargar toda la página al requerir casos puntuales solamente, pero se vuelven a cargar esos datos una y otra vez cuando simplemente tan solo deberían ocultarse.
Un ejemplo mejor puedes verlo aquí:
Ajax: Galería de imágenes paginada...
Sobre la pregunta concreta, pues no creo que sea problema ajax, sino javascript, deberías crear una capa oculta con una imagen que te guste para centrar y que represente esa espera (por ejemplo un reloj... tal vez de arena...) que rellene la pantalla, y tenerla oculta hasta que se haga la petición Ajax. Luego, al momento de recoger los resultados volverla a ocultar.
Saludos
