What? Deleting a game using usbloadergx or wii backup manager should be no different than using windows. None of the three blank out the exact data the file used, they only flags the file as deleted and the space as "free". I'm not saying it didn't corrupt another game or anything, but it wouldn't be all of his Wii games, and rather unlikely if the gc games work. If it (the HDD) was formatted as WBFS, I'd be inclined to agree as I had the same issue back then.
My cousins Wii did this crap. I just deleted all traces of usbloadergx from sd card and put it back on from the latest archive, problem solved. In any case, what commands are you using with chkdsk?
Edit: I'm not trying to be a dick Mysterio, I've just never heard of such a thing happening as that on Fat32 or NTFS. Like file corruption yes, but not every other file in the same folder structure unless like you said the hdd is problematic/corrupt. But his gc games shouldn't load if that was the case.