Gracias Seppo por tu ayuda, Ya conseguí resolver el problema, resulta que al cambiar de página no se estaban mandando los valores de las variables. por si a alguien le nteresa el problema se resuelve así:
echo "<a class='p' href='".$_SERVER["PHP_SELF"]."?pagina=".$i."&orden=".$orden."&sel=".$sel."&inf =".$inf."'>";
echo "<font face='verdana' size='-1'> Registro ".$i."</font></a> ";
PD: cambié el nombre de la variable que recogía los valores, antes era busqueda_seleccion y busqueda_informacion, y ahora puse sel e inf.