Interesting that though uninstalling and reinstalling the Google app fixes the problem I don't think that, in my case at least, is the cause. I was trying to find a couple of toddler games the other day which involved installing and uninstalling a number from the play store and I realised the icons had disappeared again. Can't be specific about which one, though I suspect it might be any of them because I had my suspicions that similar might have been the cause the first time it happened. Uninstalling the game didn't fix it but uninstalling and reinstalling the Google app updates does. So in my case its the fix not the cause.
Thought you might be interested to know.