Erm, quick tech-check: the "message" one can add to a transaction, is that stored in the scripting area?

If it is, and you need to get rid of it, maybe there's a way to use the bitcoin addresses as a nonce to secure the external service?  Publishing sign( nonce concat hash( latest_database ) ) should be almost as good...  it's might be easier to pin the external service in time by silencing the publication of the signature?