Adding a nonce to the request and storing it is a good idea to add to prevent replay attacks. Especially in the case of OAuth where some implementations hash the query string but don't hash the request body - which could allow all kinds of mischief without even cracking the secret key.