uffff... Si buscaras en los Foros, encontrarias un post Viejisimo mio con el mismo problema... :D que tiempos aquellos.
Sucede que es un "bug" del IIS. Hay que acordarse, que las cabeceras HTTP se envian en el IIS, en el sentido INVERSO al que se definen en el codigo, por eso, tu cabecera "location" se envia ANTES que la cabecera que destruye la cookie. Es raro, pero es asi.
Por eso, lo que yo tuve que hacer para solucionar eso, fue cambiar "location" por "refresh", asi :
Código PHP:
<?php
setcookie($cook,'',time()-60); //Destruimos cookie
header("Refresh: o,URL=pagina.php");
?>
Y con eso si vas a poder destruir la cookie y redireccionar.
Saludos.