I always use a VPN so I am not worried about my IP address getting listed somewhere but I only hope Google does delete my search history... Yeah I'm on that list now.
Many VPNs do actually leak your IP address. Beyond that, your VPN traffic could be associated with your billing information for said VPN. Also by coresponding the traffic to the VPN and coming out of the VPN. Or if you have any personal information associated with your Google account or have ever accessed it with an IP associated with you.
Look out the window. They're in the ice cream truck.
"your VPN traffic could be associated with your billing information for said VPN" - that's why I asked a friend from a completely different country to sign up for me (we are good friends with high technical prowess and he knows what he's up to).
I'm reminded of a Usenet campaign in the mid-late 90s, adding hot terms to sigs.