La sesión de PHP entra en conflicto con AJAX

Si entiendo esto correctamente, parece que está configurando el token para cada solicitud. Supongo que la página anterior todavía tiene el token anterior. Verificaría si el token está configurado antes de eliminarlo automáticamente.

 if (isset($_SESSION['token'])){
    //do nothing
 } else{
   $_SESSION['token'] = md5(rand());
 }

Editar Para responder a su pregunta.

En lugar de usar solo una clave de "token", cree una clave para cada sesión del navegador.

$_SESSION[$sessionId] = md5(rand());

El truco, por supuesto, será averiguar cuándo suceden porque si no puede usar la sesión, realmente no sabrá si la solicitud proviene de una pestaña nueva o de una antigua. Podría usar la cadena de consulta para pasar este parámetro. Básicamente, todas las solicitudes tendrían que tener este parámetro; de lo contrario, no asociaría una sesión con ellas.

por ejemplo

http://www.yoursite.com/somepage.php?sessionid=<some generated id>

En última instancia, el usuario podría jugar con esto, pero no estoy seguro de que haya alguna forma de evitarlo.

Editar 2 Ok, aquí está mi idea de cómo deberías hacer esto. Expertos en seguridad, siéntanse libres de criticarme si me equivoco, como dije antes, no soy un experto, pero no parece que vaya a salir de esto sin sugerir algo;-)

El problema con CSFR es que algún usuario malintencionado, Bob, podría crear un elemento en otro sitio que haga que el navegador de Alice realice una solicitud a otro sitio y, debido a que Alice había iniciado sesión previamente y esa información se almacena como una cookie o como Alice se reconoce a través de la sesión, el sitio ejecuta la solicitud como si Alice la hubiera solicitado. Por ejemplo, si el banco de Alice es http://www.mybank.com , Bob podría crear una publicación en el foro que contenga

<img srg="http://www.mybank.com/transferfunds.php?amount=1000&receiver=Bob" />

El banco de Alice reconocería su navegador haciendo la solicitud, pensando que es ella. Hay un par de cosas clave que deben suceder (juntas, cualquiera de estas fallas hará que el ataque falle) para que este sea un ataque viable (estas son las claves para entender cómo prevenirlo):

1. Alice debe haber iniciado sesión en el sitio de su banco para que el banco la recuerde. Esto podría suceder en una cookie ("recordarme") o mediante una sesión. Sin embargo, si cierra su navegador (finaliza la sesión) o borra sus cookies, no hay peligro porque el sitio del banco no la reconocerá y denegará la solicitud.
2. Bob debe poder proporcionar todos los parámetros necesarios para la solicitud; de lo contrario, el sitio web del banco rechazará la solicitud.

Para proporcionar una noción de "estado" además de un protocolo sin estado (HTTP), realmente no puede evitar el riesgo en (1). A menos que haga que las personas siempre hagan clic en "cerrar sesión" o cierren su ventana, etc., no hay nada que pueda hacer para evitar el almacenamiento de información en el navegador o la sesión. Sin embargo, puede evitar que (2) sea un problema. Mi solución a esto (y estoy seguro de que hay muchas otras) es generar un hash, como lo está haciendo y almacenarlo en la sesión.

Por ejemplo,

$_SESSION['token'] = md5(rand());

Luego, lo que hace es agregar ese token a todos sus enlaces internos.

http://www.mysite.com/secure.php?token=giuwnrefviunslfghahgliuwnvwrgbaasd

//note, you'll want to sanitize user input, I'm just being brief
if ($_GET['token'] != $_SESSION['token']){
   //User either attempted to enter a link on their own or it's a CSRF attack
   header('HTTP/1.1 403 Forbidden');
 }else{
 //do whatever needs to be done
 }