How can I ensure Firefox history is completely deleted after exiting?

I have set the option to clear my browsing history when I exit Firefox, but it does not clear completely. When I re-open Firefox, my History panel is clear but the address bar auto-completes websites which I visited in the past (and are not in my bookmarks). Old URLs must still be saved somewhere.

Additional information:

• I have disabled all my firefox extentions and still have this problem.
• I have experienced this problem with both firefox 20 and 21

Update: similar problem report: link

Solution 1:

This might provide you with an answer: Locked or damaged places.sqlite

Firefox stores history and bookmarks in a database called places.sqlite. If this is damaged, deleting history or even adding something to bookmarks might have no effect.

Solution 2:

• In the Preference or Options dialog choose "Never remember history".

• You can switch to always browse in private mode, this will effectively do the same but you will be surer about it and won't need to change any settings.