Vale, al final lo he solucionado de la siguiente manera por si a alguien le interesa:
Código PHP:
Ver original//SI SOLO HAY UNA PALABRA DE BUSQUEDA SE ESTABLECE UNA INSTRUCION CON LIKE
$cadbusca="SELECT * FROM $bd.contacto WHERE nombre LIKE '%$busqueda%' OR apellidos LIKE '%$busqueda%' OR email_empresa LIKE '%$busqueda%' LIMIT $RegistrosAEmpezar, $RegistrosAMostrar";
//$filas = mysql_num_rows($consulta);
$cadfilas="SELECT count(*) FROM $bd.contacto WHERE nombre LIKE '%$busqueda%' OR apellidos LIKE '%$busqueda%' OR email_empresa LIKE '%$busqueda%'";
echo $cadfilas."<br>";
$filas = $f[0];
Es decir, he hecho una consulta a parte con un COUNT(*) que te devuelve los resultados, y lo he aprovechado para que te de las filas.
Gracias a gnzsoloyo por tu respuesta ;)