Sounds like what I jokingly call "Muldaur Pixels", but "CSI" works too. The lab always seems to create perfect license numbers from 9 pixels...
The only thing I can think of is to try some resampling when increasing the number of pixels (or >100% scaling). Preview only has "resample" on/off, but if you have Photoshop, you can change the algorithm and their settings.