Тестировали на разных компьютерах в разных браузерах?
Локально и на хостинге поведение одинаковое?
1) В браузере есть настройка "Уничтожать куки после выхода из браузера"
2) Может быть, мало места на диске компа, с которого заходите
3) Погуглите, какие есть настройки в .htaccess/php.ini, связанные с куками
Возможно, что кроме
php_value session.cookie_lifetime 1200
php_value session.gc_maxlifetime 1200
есть что-то еще
У меня была такая проблема, делал несколько сайтов на одном коде, все работало, а потом перестали вешаться куки. Оказалось, хостер изменил дефолтное значение в php.ini каких-то из этих параметров
php.net/manual/en/session.security.ini.php (сейчас уж не помню каких).
Пройдитесь по ним. Если локально работает, а на внешнем не работает, то сравните локальную конфигурацию с внешней. Особенно вот эту настройку
session.use_only_cookies гляньте
4) Помню, у одного юзера все время крашились куки в разных браузерах. Помогла только замена компа.