Estamos ante 2 cuestiones
1° El tiempo de vida de la sesion es menor al esperado
Imorap, esto me huele a que tu estas haciendo un session_destroy en algun lugar que no es conveniente.
Puedes revisar eso? o pasar un poco mas de codigo.
Luego He visto tu codigo:
2° Aparentemente la sesion no es destruida
La sesion si esta siendo destruida, lo que ocurre es que se conserva el mismo session_id gracias a que el navegador sigue enviando la cookie de sesion. Pero esto no es un problema porque al hacer el session_destroy() todo contedino de la sesion es eliminado: Lo que ocurre que al hacer el session start se reutiliza el session_id anterior gracias a que este es tomado de la cookie.