Well this is hard to tell.
The might have another way of tracking you.
Knowing google, thell track you anyway anywhere and everything.
Thats google, biggest database in the world in the hands of a private corp.
Its like a dream come true.
No but really, just delete your cookies.
Use no referer , noscript , browser agent spoofing, 'google sharing' (moxie marlinspike).
Trackmenot is interesting.
Man my firefox is stuffed with these addons, well if thats what it takes these days.
Also use midori for other stuff