Sounds plausible. No matter what they say, Google "stickies" some searches to IPs, even when you're not logged in and clear all cookies. This is one of the reasons I started using a VPN.
Your actual identity is irrelevant, it's the "virtual" identity they've built of you that's important.