>This reminds me of a friend of mine who proxies all his web traffic through something which strips user agents and referrers. It's very easy for me to tell when he visits my website, because the logs show "-" for each of these fields.

I wonder if the best strategy, then, is to figure out a very common user agent string and use that. The EFF's Panopticlick might be a good start: https://panopticlick.eff.org.