Here's an easy, and verifiable, way to destroy coins:

Take the reference code, apply RIPEMD-160 and encode it as an address. Do a transaction which sends a satoshi to this address, and the the coins-to-destroy to 1BitcoinEaterAddressDontSendf59kuE.

You can then view them in a block explorer using the invalid address: http://blockchain.info/tx/f374fb91ea29b02d295d535da537c7770caa71c4937095c51467b4d8b1b60c1b

Signing a message with the address used to send can also be employed as extra verification