Over time, we saw that people didn't seem to notice/care about the message and corresponding link much, so it eventually migrated down to the bottom of the search results.
Instead, you could have tried to make it more prominent by (for instance) moving it to the upper left rather than the upper right of the search results, right above/below the ads.
Another issue that might be interesting to explore is to what extent users really understand what search customization is, and whether they'd care more or less about it being done automatically once they understood it better.
I have a feeling the vast majority of them probably wouldn't care, and take the attitude of "do whatever it takes to make the results you return more relevant, and I don't really care how."
But the real solution is to use a search engine that does not track you. Even better is to use it in such a way that it can't track you (ie. through a Tor proxy, while taking other reasonable precautions).