Es muy extraño lo que te sucede porque yo para eliminar la Cookie hago lo mismo que tu.
<pre> function eliminar_cookie()
{
#eliminar el cookie es ponerlo a un valor nulo
setcookie("MiGalletita","",tim e()+(60*60*24*365));
} </pre>
Es extraño que no se puedan eliminar las cookies de otra forma más limpia.