How do you know neither of those options deleted Cookies?

1. Does this behavior persist if you start IE7 in No Add-ons mode?  To start
IE7 in No Add-ons mode:

Right-click on the blue IE desktop icon and select Start without Add-ons; or

Start > (All) Programs > Accessories > System Tools > Internet Explorer (No
add-ons).

Troubleshooting and Internet Explorer’s (No Add-ons) Mode:
http://blogs.msdn.com/ie/archive/2006/07/25/678113.aspx

2. Does the problem persist if you Reset IE7 Settings (RIES)?
http://support.microsoft.com/kb/923737 <= Read before using!

3. If you uninstall (a) IE7 *exactly* per the link below (which
automatically returns you to IE6), (b) all toolbars and (c) all third-party
Windows Themes (including Window Blinds) and do NOT reinstall IE7, does this
behavior persist?  If it does, do NOT reinstall IE7.

Uninstalling IE7
http://www.ie-vista.com/kbase2.html
[Only use the Command %windir%\ie7\spuninst\spuninst.exe if you cannot
uninstall via Add/Remove Programs!]

IE7 (Un)Installation and Anti-Malware Applications:
http://blogs.msdn.com/ie/archive/2006/10/11/IE7-Installation-and-Anti_2D00_Malwa
re-Applications.aspx

4. Required reading IMHO before reinstalling IE7:

Sandi's Installation Tips <= Steps #1-8, #10 & #11; take note of #12, then
STOP
http://www.ie-vista.com/known_issues.html#pre-install

I strongly recommend using
http://www.microsoft.com/windows/downloads/ie/getitnow.mspx as the
installation source, not Automatic/Windows Update.

Direct Download link:
http://www.microsoft.com/downloads/details.aspx?familyid=9ae91ebe-3385-447c-8a30
-081805b2f90b

Tip: Save the installer to your desktop, do not Run it.

5. Make *certain* that you check in at Windows Update immediately after
reinstalling IE7 to install any critical updates offered.  If Optional
Updates category offers Root Certificates update, I recommend installing it
to take full advantage of IE7's additional security.

That's you IE version.
What's your Windows version and Service Pack level?