Windows stores URL, cookie info in a file called index.dat as well. This can not be deleted when the computer is running, could also be for some odd reason why those other cookies can not be deleted, but most likely this could be some spyware, foistware tactic.
You may need to check the file attributes, and remove those that state read-only.
The best way to delete any stubborn file is via DOS.