I don't think you want to detect if they are behind a proxy, because there are many legitimate reasons for being behind a proxy (I'm using one right now).

However, you may want to see if they're behind an open proxy (a proxy that will allow anyone to relay a connection through it). If that is the case then they are more likely to be trying to hide the true origin of their request, and open proxies are generally run by people who either didn't mean for them to be open or just don't care, so you're not likely to be able to track down someone who uses one.

To detect that, you could attempt to connect to several commonly used proxy ports on that IP address (see the IANA ports assignment page for a good starting point), then if the connection is successful, deny their request. One disadvantage that this would have is that some people may be running intrusion detection systems that see this as an attack on their system.

Another option would be to use an already compiled list of open proxies (which is probably how they found the open proxy they're using). There are good ones at http://www.openproxies.com/ and http://mikhed.narod.ru/download/lists/goodproxy.txt.