Eso pasa porque la caché de tu navegador guarda una versión de la página que la muestra al hacer clic en el botón Atrás. Sin embargo, si le das en Actualizar (F5), verás que en realidad tus cookies ya no existen.
Puedes forzar al navegador a
NO guardar tu página en el caché a través de PHP
Empieza por
php+evitar cache
Un saludo,