Interesting — does iCloud otherwise work normally? We've used it heavily for years and never seen anything like that. They used to have an option in the iCloud.com settings (under advanced) to reset the sync system which might be worth looking for — back in the day there used to be a utility to reset the Mac sync database which often fixed problems like this but I believe that was removed at some point.