So it seems OS X keeps track of all your downloads (even if you are using the Incognito/Private Browsing mode of your browser).
It stores the information in the following files:
- ~/Library/Preferences/com.apple.LaunchServices.QuarantineEventsV2 on Lion
- ~/Library/Preferences/com.apple.LaunchServices.QuarantineEvents on Snow Leopard
They are SQLite databases and can be manipulated with the right tools.
So to delete all the contents you need to open the file for your version of OS X (Lion in my case).
In the SQLite console delete all entries in the one table it contains.
delete from LSQuarantineEvent where 1=1;
This statement works in either file, but if you have Lion you might as well get rid of the old file.