You can print out a wallet with a specified amount (a la http://forum.bitcoin.org/index.php?topic=20917.0 or http://forum.bitcoin.org/?topic=3716.0) and say the sale is for the redeemable bill. You will be able to prove with blockexplorer when this bill is consumed.
What stops me as a Bitcoin seller from keeping a backup copy of that wallet? 
Also as it has been pointed out, if you sell a certificate, gift card or whatever, then that's what the other person pays for. Not bitcoins.