Switch to Mozilla/Netscape. They use a single cookie file, COOKIES.TXT. As long as you back it up, you can safely edit it with an ASCII text editor to remove any hostile cookies.
Spyware removal software often finds hostile cookies. Since some sites only work with IE, I have it set not to accept cookies. If I need them for a site, I manually turn them on for the time I'm on the site. Then, I turn them off, again. To make sure I'm clean, I run a bat file at startup that deletes all IE cookies with every reboot.
I don't mind manually logging onto sites so on my system, my NS cookie file is a zero byte read-only file, and I set my browser to accept all cookies. I have no problems with sites that otherwise work with NS.