El problema no son las sessiones, sino las cookies que ahora IE 6 se ha puesto más chulo con las cookies (galletas) y para que las cookies que creas te las acepte como buenas (en el nivel de privacidad) tienes que enviar la cabecera indicando ese protocolo de privacidad.
Código PHP:
header('P3P: CP="NOI ADM DEV PSAi COM NAV OUR OTRo STP IND DEM"');
Más información
aquí
PD: Cada palabra tiene su sentido en lo de CP="....." no esta puesto por ponerlo :D