problema con buscador en php

[educacanis]

Hola buenas,
tengo un nuevo problemilla. He estado intentando hacer un buscador con varias listas desplegables de manera que me filtre una busqueda en una base de datos en MySQL.
El formulario de busqueda tiene dos listas desplegables y para que me filtre la busqueda tengo el siguiente código

Código PHP:

  if($_GET['Tipo'] == 'TODO'){
    if($_GET['Provincia'] == 'TODAS') {
    $query_DetailRS2 = "SELECT * FROM establecimientos ORDER BY rand($rand)";
    } else {
    $query_DetailRS2 = "SELECT * FROM establecimientos WHERE ID LIKE '$Provincia%' ORDER BY ID DESC"; 
    }
}else{ 
$query_DetailRS2 = "SELECT * FROM establecimientos WHERE ID LIKE '$Provincia%' AND Tipo = '$Tipo' ORDER BY ID DESC";
} 
   

el formulario me funciona perfectamente, pero las búsqueda está dividida de manera que en cada página me muestre 20 resultados. Cuando tenía la página del buscador de manera simple me pasaba de una página a otra de la consulta sin problemas, pero cuando ahora le doy para que pase a la página siguiente me sale que no tiene resultados.

Creo que es porque vuelve a hacerme todo el if y como se "reinicia" el formulario hace cosas raras...

La verdad es que no sé porque me falla...ni siquiera sé si la parte del código que os he puesto es la que tiene el problema
Alguien puede ayudarme??'