Art indeed. Somewhere between the 10 year old camera and the Flashair card of questionable origin these artifacts get introduced.
That's quite odd.
I would not be at all surprised if the flashair deleting files had unexpected side effects, since the camera likely has in-memory state related to the filesystem which isn't aware of the flashair, but valid-but-corrupt images doesn't seem like the most likely outcome.
It would be interesting to see an original image from when this happens. Also, you using camera jpegs or CHDK raw?