En la documentación oficial de PHP .. hablan de "matar" la cookie (manualmente) que crea PHP (si propagas el SID en cookies) además de deshacerte de la sesión como ya lo haces (con el session_destroy() y el unset() ..) pruebalo por si tienes problemas con esa cookie:
www.php.net/session_destroy
(lo tienes en los comentarios de los usuarios de dicha función)
Un saludo,