In this paper, we argue that weak cache consistency mechanisms supported by existing web proxy caches must be augmented by strong consistency mechanisms to support the growing diversity in application requirements. Existing strong consistency mechanisms are not appealing for web environments due to their large state space or control message overhead. We focus on the lease approach that balances these tradeoffs and present analytical models and policies for determining the optimal lease duration. We present extensions to the http protocol to incorporate leases and then implement our techniques in the Squid proxy cache and the Apache web server. Our experimental evaluation of the leases approach shows that: (i) our techniques impose modest overheads even for long leases (a lease duration of 1 hour requires state to be maintained for 1030 leases and imposes an per-object overhead of a control message every 33 minutes); (ii) leases yields a 138-425\% improvement over existing strong consistency mechanisms; and (iii) the implementation overhead of leases is comparable to existing weak consistency mechanisms.