Метод Cookies.Remove удаляет cookie из коллекции на сервере. Естественно, у клиента при этом всё остаётся без изменений. Чтобы удалить cookie с клиента нужно создавать новый объект HttpCookie с тем же именем и задать Expires в прошедшую дату:

if (Request.Cookies["Key"] != null)
{
    var cookie = new HttpCookie("Key")
        {
            Expires = DateTime.Now.AddDays(-1d)
        };
    Response.Cookies.Add(cookie);
}