From what I can tell it is not a real bug but a regression that's part of a new feature RichResults. The browsing history does not erase RichResults anymore. If you don't want RichResults keep track of where you went, in Firefox you need to enter

about:config
and then scroll down to:
browser.urlbar.maxRichResults
and change the default.
The default setting is 12 and if you want nothing, you enter 0.

Refusal of the "RichResults" to obey the "Clear Private Data" command presents a significant privacy issue in Firefox 3. Read a message board on Ubuntu dedicated to this issue.