depends on how anonymous they are. if they're 100% anonymous, i don't think you have much to do - maybe only test the ip's in a proxy database - not sure where you'd find that, especially that they change so quickly.
BUT. for the less anonymous ones, the "HTTP Forwarded For" IP information should be different than the "host address" IP. you could have a small script to test that and if the values are different, block the access.
to see what i mean, try to use a non-anonymous proxy on
http://ipid.shat.net/ .
this could reduce the number of your visitors though. some companies and even ISPs use proxies.