Handling redaction (that is, confirming the authenticity of arbitrary fragments of PMs) messes up the simplicity of the above approach, and makes things pretty gnarly. I can think of a handful of ways to make it work, but one non-technical concern I have is people building cases against each other based on "verified" but out-of-context and/or intentionally-misleading PM fragments. On that basis, I'm tempted to avoid the redaction quagmire altogether and just stick to a simple all-or-nothing approach to proving PM authenticity.
I've had more recent ideas like adding a new BBCode tag (named vquotepm, or something) that would render in a different style/color compared to regular quote tags and that would be used to quote "verified" PMs (verified in the sense that the server confirmed the quote's correspondence-to-source before embedding a digital signature to that effect).
(And finally, my most recent thought is to not do any of the above, and just fold PM-authentication into PM-exporting: that is, when I get around to tackling that, I'll look into ways to allow the download of some kind of server-signed authenticity-proving data, too.)