This looks like the onboard NAND flash is corrupt. If it never worked from the beginning, then chances are you got a bad chip (or it was damaged in shipping somehow). The "not found" errors give it away, and the "wrong dataCRC" error confirms suspicions. Since the problem is gradually getting worse, it's either the hardware or a corrupt filesystem (but if it didn't work since you got it, corrupt hardware is the more likely culprit).
Gumstix has ( I believe) a 30-day warranty, but from how it sounds you already passed that mark.
Microsoft is not the answer.
Microsoft is the question.
"No" or "Linux" is the answer.