"Defacing" bills is against US law but it hasn't really been enforced:
http://en.wikipedia.org/wiki/Where%27s_George%3F#ControversyI'm afraid blatantly encouraging individuals to do this would give the Secret Service a reason to prosecute bitcoiners, even if it's a flimsy one.
I still prefer keeping it very simple.
Person finds bill with URL, visits website, enters serial numbers, possibly wins BTC.
Person learns that even unmarked bills may unlock BTC.
Person visits site often to check bills, investigates the BTC market and becomes immersed in the bitcoin community.
Person becomes an advocate of bitcoin themselves and begins proselytizing and spreading the word with bills marked with the URL.
Contests over how many bills you've marked, how far they've traveled, etc should just be gravy.
Again though, how would you prevent people from making up serial numbers?
The first time a note is entered, it CANNOT give out BTC, or else people will just start making up serial numbers.
I agree with edd about keeping things simple, but actually the game I described is no different in simplicity from a user's perspective. They're still just entering bills into a site. The site does all the rest of the work for calculations.
I also agree a note can't give credit the first time entered, or people will make up serial numbers. I think the key validation is having the second person verify the details of the bill. From the tech standpoint checking the I.P. geo location is the best way to guard against one person pretending to be many others.
As for the illegality of marking bills it's interesting that wheresgeorge.com has set a precedent. The Secret Service themselves commented that as long as the site ceased selling the rubber stamps to mark with they wouldn't look into it too much. If bitcoin created its own game that did nothing different what would justify a new crack down?
It's a gray area, but it's interesting that the current system has no problem using gray area to their own benefit, such as with so-called "voluntary" income taxes and capital gains taxes on legal tender gold/silver coins.
The anonymous features of Bitcoin makes it possible to safely take a political stand. It's just a question of whether the resulting PR would do more harm than any benefits of exposure from actions taken.