Buenas,
La respuesta a todos tus males la tienes al principio del código...
Cita: <?php
/* Abre Coneccion MySQL */
include('includes/conexion.php');
if (!isset($_GET[pag])) $_GET[pag] = 1;
?>
Has creado una variable de SESSION con el fin de traspasar la variable de la página de resultados a cargar... La única cosa que faltaría con el fin de mostrar el titulo personalizado con el nº de página es simplemente añadir a la etiqueta <TITLE> .oO(Que no he sido capaz de localizar ... ¿? ) añadir lo siguiente:
Cita: <title="TITULO DE LA CATEGORIA QUE SEA - <? echo $_GET[pag]; ?>"</title>
De esta manera en la paginación de resultados se añadirá en el titulo el nº de página y no experimentarás ningún problema.
Por otro lado, y dandole un par de vueltas a todo lo comentado en este post, me parece extraño que te hayan penalizado o hayas experimentado perdida en el posicionamiento de resultados de busqueda por este tema en concreto, ya que aunque tengas exactamente el mismo titulo en todas las páginas de resultados el contenido y la URL no son la misma... no se, un tanto extraño no?
Espero que te haya podido servir de ayuda! ;) Si quieres profundizar más en el tema del código, será mejor que abras un post en el foro PHP
Saludos!