Tudo bem, descobri qual era o problema. O relógio do servidor estava desligado por várias horas e acredito que o Internet Explorer reforce rigorosamente o horário do servidor. Então todos os cookies estavam expirando imediatamente.
Eu usei este artigo para corrigir a hora do meu servidor e tudo funciona perfeitamente agora.
Como faço para atualizar o tempo de um servidor CentOS de um servidor de horário autoritativo?