While you might not be able to construct the entire banknote, there would probably be a high chance of many partial constructions. In and of itself interesting from a partially complete puzzle perspective. Plus, attempting to match varying serial numbers, dates, reference marks, while still having each bill vary.
Could probably be improved by doing 50-100 variations on each bill to give a general idea of the patterns possible within a zone. Such as: This area has 8 possible characters, with 36 possible entries /[a-zA-Z0-9]/. It has a fixed border with some constant pattern nearby. Show all the possible combos and then dice up the area a bunch of different ways.
On the partial constructions topic:
You have 350 of 1000 pieces of an image with some known general shape.
How much of the image can you reconstruct while still missing 2/3 of the pieces?
At the least has applications for image guessing. Also, agree on the false bank note contents, and how many people at the note shredding office are just stuffing their pockets with bank notes and then filling the cylinders with rocks? Great scam that probably almost nobody actually checks.