The context of this thread is creating a Posterous-style email validation. Posterous does not use either of the two solutions that you suggest.
It's OK that DKIM is not widely deployed because the logic falls back to other mechanisms when the DKIM header is not present. DKIM is deployed on GMail and Yahoo Mail, so it is worth doing. Replay attacks are easy to defeat by not posting duplicate content. It's probably a good idea do to dup detection to handle the case where the user accidentally sends the message twice.