Let's see, how we can fix that in Ubuntu (11.10).
Luckily, nearly all questionable history (movies watched, documents opened, ...) are recorded in the same file named recently-used.xbel .
Do the following commands to delete the file containing history, and then recreate an empty file with same name:
sudo rm -rf ~/.local/share/recentyl-used.xbel
sudo touch ~/.local/share/recently-used.xbel
Your history is now clear, but any new actions will be noted in the file, so further modification is needed to stop that.
This will disable history logging:
sudo chattr +i ~/.local/share/recently-used.xbel
This will enable historry logging (if you change your mind later on):
sudo chattr -i ~/.local/share/recently-used.xbel
I'll post about clearing Terminal history tomorrow.-