"clear all current history" is leaving some history intact
Some websites still know that you are the same user despite clearing the history and changing the connection externally (with Vidalia). The only solution is to get a "New Identity", which loses all your tabs and downloads.
Trac:
Username: Richard