You didn't mention your Windows version. That's critical to any question
regarding IE, which is effectively a different program on each version of
Windows.
Did you close IE before checking the Cookie folder? IE makes most of its
actual file changes when it exits.
Are you sure that you're looking at the right folder? If you're running
Win XP or 2000, there may be more than one. If you have multiple users
defined, there's cetainly more than one. My system has 6.
If you're looking at the right folder and Delete All Cookies doesn't
remove them, then it's likely that the index.dat file has been corrupted
or gotten out of sync with the folder contents. There's a fix, but how
you go about it is dependent on your Windows version.