Mike, do not answer this yet. Let me edit it with the "crossing system" you proposed...
Person 1:
Create a random private key (a)
From the random private key calculate the standard public key (A = a*G)
Print the private key (a) on the bill and cover it with a sticker
Send the bill, along with the corresponding public key (A), to person 2
Person 2:
Create a second private key (b)
From the random private key (b) and the public key created by person 1 (A) calculate the final public key (B = b*A)
[Note b*A = b*a*G which makes the final private key b*a]
Print the private key (b) on the bill - As you said this could be left in the clear if you want to
Calculate the public key address of public key B and print it on the bill
Fund the public key address with the correct number of BTC
I hate to gum up the works, but there is one flaw. If I ever can see the full printed bill in circulation, and I was an evil person who actually was saving private keys, since the second one is in the clear, I would have both, and thus would be back in the beginning again (except with a new layer of trust in the bills).
How I could be evil, is buy these under a false name, have Mike ship them, and then somehow pass them off again to someone else to resell them or spend them.
Yep, it is far fetched, but I predict that in the next two years their will be a boatload of people printing all sorts of bitcoin bills, and this little run-around might become feasible.
Since Mike and I are the only game in town at the moment, and it would be absurd to go through all these steps where I could achieve the same ends without any steps, it should be just fine to use the clear second half of the private key. I would just recommend that when this becomes a common practice, both private keys need to be obscured.