Why not have a qr code that links to a site that will accept that note and give bitcoins in return? (e.g. TO CONVERT THIS NOTE TO BITCOIN, SCAN HERE)
A bit tricky to do: how do you regulate the transaction? Pointing to an exchange will be wortless for a new user (registration and money transfer to obtain something that don't know how to use.
It can worth something maybe pointing to an informative site like weusecoins.org and put a small reward (some satoshi) on every bill redemable from it (but again a lot of work to do: every note shall have a different code, or there will be a database of note numbers to avoid that someone use the same bill a lot of times). Not to mention that writing on note could be illegal in some countries so have a clear and direct connection from the altered note to a specific site could cause some legal problem.
