On the nonce-tracking front, what about a monotonic counter?
The client can generate the next nonce by incrementing the previous nonce value.
The server only needs to remember the highest nonce it's ever seen, for a particular session, and reject any new nonces less than or equal to it. O(1) in time and space, and no need for anything clever like bloom filters.
Edit: One issue I can see with this approach would be, what if requests arrive (or are processed) out-of-order? You'd perhaps want to track a small window of nonces to account for this.