So you want to rate limit users. You really don't need to encrypt the message, then. You need a balancer.
If this is due to concerns about high traffic, you better implement it outside your server and use sth like haproxy, lighttpd or nginx. Nginx by default limits requests to 50/minute per IP, and redirects to a customizable 503 page. If IP suits you as an identity, that will be enough.
If IP isn't good, you can accept only requests with a solid key, then use haproxy as the sole balancer, or maybe [3scale][1]3scale which also provides analytics.
If high traffic or DoS, DDoS attacks are a concern for you, you can also use an apache server with [mod_evasive][2]mod_evasive as part of your proxy.
Finally, to be honest, there are so many possibilities that the IP is not a trustable id (NAT, users changing their IPs, even MACs). Since your main problem appears to be a decent authentication solution, why don't you use OpenID and a balancer? [1]: http://www.3scale.net [2]:
Edit:
Nginx has also a http://www.zdziarski.com/blog/?page_id=442limit_proxy_xuid option, which can be up to 255 characters, to limit traffic.