anche io pensavo che il cookie non doveva avere informazioni sull'utente, ma non è cosi, perchè se il cookie lo elimino i fisicamente il logout lo fa correttamente.
cmq se vuoi provare iscriviti al sito www.forumphp.it e prova a fare il logout, vedrai che non lo fa. poi togli il cookie PHPSESSID manualmente e vedi che il logout funziona.
comunque la sessione la gestsco così:

<?
session_start();

....../*prelevo le informazioni dal database del 'utente
che si è loggato e le metto dentro $_session[user]*/
?>

per il Logout faccio soltanto:

<?
........
unset($_session);
session_destroy();
........
?>