Steam-Auto-Cloud not working when reinstalling game

Hey,
I turned on the Steam-Auto-Cloud option for my game and I can see that save files are updated to the cloud. But players that e.g. reinstalled windows don’t have their cloud files downloaded on their PC and so their save files are lost. I’m not sure what to do about it. Any one had problems related to that or a working implementation?