I was looking for a much simpler idea though. Like a simple handwritten IOU. ....backed by Bitcoin.
Unless there was some security built into the paper system, I would never accept it, *except* if I was accepting it from the (trusted) issuer. Even if my most excellent trusted friend tried to give me one, I wouldn't accept it because, even though he's acting in good faith, the note might have already been cashed in (or copied, whatever) by some nasty previous holder. Also, I wouldn't accept a token that couldn't be automatically redeemed - otherwise the other party to my transaction could give me the token, I'd check the (visible) address to see that it was still valuable, but then the other party could redeem it, from a copy, after 10 minutes. I'd want to secure the funds in my own wallet immediately - for me, that's what the transaction is: putting funds into my wallet.
...it's someone who wants to copy a key before passing now-useless cash on to some poor sap.
I think no matter what you do, it's going to be somewhere between difficult and impossible to make physical bitcoins that don't carry the risk that they've already been digitally spen. It boils down to being given an object which is said to have value, but which becomes worthless through an action that can be done without physical access to the object.
The token must be visibly destroyed for redemption. But you can always check that the coins haven't been spent by checking the visible address against the blockchain. So any attacker only has time to cheat you from the moment you accept the token to the time you try to redeem it. This time should be made as short as possible, therefore, automatically redeemable tokens, NOT requiring you to return them to the issuer.