I use a VPN service that provides a pool of IP addresses, I clean history/cookies/etc - all the browsing data before a session.
Regardless, when I type in the search of one particular search engine, I begin to receive personalized suggestions that, for sure, are based on my previous queries as these suggestions are very rare and surely cannot be common.
I use FireFox as a browser, with standard settings and without addons. I am not using any accounts like a Google account.
How can either FireFox or the Search Engine know my history under the aforementioned circumstances?
And how can I make my VPN sessions unique (providing they do have unique IPs) for web-servers?