If they are never redeemed they could be double issued. And when it came time to prove it the issues could just say it's a counterfeit.
If no paper notes are ever redeemed they could be double issued.
But if a (small) part of the notes are in fact redeemed this would force the issuer to not double issue notes.
Otherwise if a non-backed note is found, this would destroy the confidence in the paper money.
It would not even be necessary to hide the private key on the note, it would actually be better without.
It could work like this:
An organization or preferably a government could issue notes with a bitcoin address printed on it along with a denomination.
The amount printed on the note should be stored in the bitcoin address of the note.
This could be verified by anyone at any time.
The notes should be redeemable to digital bitcoins without any fee.
However, the issuer could have printed several identical notes.
To make sure this is not the case, concerned citizens should redeem some notes at regular intervals.
There should only be two transactions fro each note:
One deposit at the day of printing and one spend when the note is redeemed.
If there are several deposits for the same address, this means that the issuer has cheated
and printed several identical notes.
This will make the notes as anonymous as todays fiat paper money, and would scale,
since the wast majority of transactions would be off chain.
This would give a fully backed, anonymous and scalable currency this would not be possible for a government to tamper with.
Or is there something I have not thought about?