There are many websites that provide timestamping and notary services.
http://astroblocks.com/
https://www.bitnotarize.xyz/
https://bitproof.io/
https://blocksign.com/
http://www.cryptopublicnotary.com/
http://tangible.io/
https://uproov.com/
http://virtual-notary.org/
Our current messaging can be used for timestamping and notary purposes.
To timestamp (Proof of Existence) the file:
Add a Drag and Drop function to the client.
The browser can calculate the hash of the file using Javascript.
The hash is sent in a message and recorded on the NEM blockchain.
For decentralize auditing and specialized use cases, like Proof of Process and Proof of Audit, our editable m-of-n multisig can be used.
https://tlsnotary.org/wp/
I think this can easily be integrated inside the NEM client.
This would give users an easy to use buit-in notary service. The NEM client will be a one stop shop.