None of that convinces me that its impossible for Nintendo to do. I think it is unlikely, but how in the world did the OP's game suddenly give him the error that he needs to redownload the VC game in question if he didn't even touch it and it had been working fine previously?
Perhaps it just corrupted?