Some files on my 2 Xboxes seem to get corrupted randomly after some time. I doubt the HDDs to be faulty since I bought especially new ones some years ago, after one HDD really died. The problem actually fits the OP's quite well: Games stop working, game saves stop working, files become unreadable...
It might prove interesting to check the HDDs with a windows tool, or at least read the SMART values.