Cookie-problem

OK - vi er løbet ind i et RET sært problem. Vi har en NT 4.0 (Engelsk version) server med Apache og PHP4 stående. Vi har så leget lidt med at sætte en poll op på en side, og den virker også fint på PHP3-servere. I det sekund den kommer på vores server sættes der dog ikke cookies længere - og dog. Det sære er, at der sættes cookies uden problemer i NS 4 og 6, men altså ikke i IE 4, 5 og 5.5.
Scriptet er før blevet testet på andre PHP4-servere, og virkede uden problemer. Problemet må altså ligge et sted i opsætningen af serveren, men... HVOR!?

Nogen der har været ude for noget lignenden? Vi er rendt tør for løsninger!