This shouldn't come as a surprise to anyone. Anytime you try to retrofit a new security model into an old one, you will break things, and sometimes it's just impossible to do it right. I suspect that most modern browsers will never be able to remove all possible traces of what you've been up to. There is a clever solution in Fedora 13 though. There is a tool called sandbox that Dan Walsh cooked up. I'll save the scary details, you can read Dan's blog for that.
The basic idea is that you can run a web browser inside of a sandbox, once you exit the sandbox, your files are all deleted. By using SELinux to confine the browser, you don't have to worry about an exploit breaking out of the sandbox. Since all the files are removed once you exit, there is no history left on the disk. Currently the sandbox only deletes the files written to disk, I filed a bug to shred them instead, which would prevent someone from inspecting the leftover bits on the disk.
The only trick that's no obvious, is you probably want to carry along your .mozilla directory for things like bookmarks and plugins. My sanbox browser command is