Sigo las instrucciones en http://msdn.microsoft.com/es-es/library/ms178195(v=vs.80).aspx pero la cookie no desaparece.
Solución:
Establece también el path y el dominio
El código completo sería:
Dim myCookie As HttpCookie
myCookie = New HttpCookie("miGalleta")
myCookie.Path = "/"
myCookie.Domain = ".midominio.es"
myCookie.Expires = DateTime.Now.AddDays(-1D)
Response.Cookies.Add(myCookie)
Esto es particularmente interesante para omitir las cookies de la autenticación por formulario, como las del pobre Forefront TMG.