elseif($_GET["sprovincia"]!="")
Si esperas obtener la variable "sprovincia" después de pulsar el enlace "siguiente" debes mandársela
echo " <a class='p' href='".$_SERVER["PHP_SELF"]."?pagina=".($pagina+1)."&orden=".$orden."&criteri o=".$txt_criterio."&sprovincia=".$_GET['sprovincia']."'>";
echo "<font face='verdana' size='-2'>siguiente</font></a>";
Si $_GET['provincia'] está vacío ya te recoge criterio pero si no, te debe recoger la variable sprovincia cuyo $_GET[] ya lo habrás obtenido de la consulta que proviene de tu formulario.