From the mailing list, a question about implementing nonce checking, and a reply from Brian Eaton:

1. create an expiring nonce cache. The cache should be keyed by nonce and consumer key, and possibly by access token as well (your call). Each entry in the cache should include a timestamp, and entries will be removed from the cache after some time window (say, 5 minutes) has passed.
2. When you verify requests, you first check if the timestamp is within some reasonable time window (say, 5 minutes.) If it is not, you reject the request.
3. If the request is within the time window, you check if the nonce cache contains an entry with the nonce from the request. If it does, this is a replay and you reject the request.

Making nonce-checking scale across a large number of servers is hard, since it is rapidly changing server-side state. I suspect most OAuth service providers with more than a single machine don't bother.

Time stamp checking is a good idea and is reasonably simple to implement. If you need to support clients who have out-of-sync clocks, you can implement the OAuth problem reporting extension (http://wiki.oauth.net/ProblemReporting) and return timestamp_refused.