Pues no lo he hecho nunca, pero supongo que se podría hacer así:
Tras el include("paginator.inc.php"); se puede obtener el nº de filas recuperados con
Código PHP:
$num_rows = mysql_num_rows($_pagi_result);
Aunque creo que también podrías utilizar una variable del propio paginator que contiene el nº de filas recuperados: $_pagi_totalReg
Preguntando si su valor es 0, podrías sacar el mensaje que quisieras.
Un saludo.