Check and cache ts+nonce pairs, not just plain nonces.

Fixes #426 (which is kinda irrelevant given #578 but we might as well fix it while we're mucking around here).  @dannycoates r?