I've been looking into this and have several patches along these lines. None of them address message-unique-id directly yet (I plan to tackle this soon) but they do address the general problem area. The basic idea is to use a new make-nonce primitive. I thought I'd email the patches now to see what others think about the direction they're headed.