is there anything that would protect against the seller from sending the cert, but not the credit? They'd be in the clear as far as paypal was concerned because the cert would have been delivered 
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.