I like this idea.
-snip-
Under request anyone can acquire the signature of a sent or received PM to prove authenticity. The process would be 100% automatic.
-snip-
I think a better way would be to have a button-like on every PM. Sender/receiver can click it and the signature associated with that message will be shown. The way you suggested, assuming it is automatic, may cause high server loads.