Browser-geschiedenis wissen?!?

Ok, ik dacht toch al wel behoorlijk wat meegemaakt te hebben... Maar wat ik nu toch merk vind ik wel erg vreemd. Wanneer ik m'n browser-geschiedenis in Firefox (versie 12 in Windows 7) probeer te wissen, dan blijft er toch op de één of andere manier iets achter. Het wissen gaat goed (zonder foutmeldingen), m'n geschiedenis laat ook niets meer zien, maar wanneer ik een URL begin te typen, dan wordt dit toch nog steeds automatisch aangevuld met een URL waar ik eerder ben geweest... Als ik nu bijvoorbeeld de "g" van google intyp, dan komt er een lijstje met mogelijkheden waarvan de eerste "mail.google.nl/mail" is, terwijl ik sinds het wissen van m'n geschiedenis nog niet op gmail ben geweest!

Ik wis al jaren regelmatig m'n geschiedenis, maar heb dit nog nooit meegemaakt. Iemand enig idee hoe dit komt en hoe ik m'n volledige geschiedenis kan wissen?