Thanks to this reddit post for giving me the info I needed: https://www.reddit.com/r/Steam/comments/1esokbd/comment/lkmzarq/

Normally, when installing a game through steam, steam downloads a .ico file and places it in <steamfolder>\steam\games

This icon file is then used for steam's desktop shortcuts.

However, games can be added to steam through other means: For example, when re-adding old steamlibrary folders after windows was re-installed, or from a hard drive transferred from another computer.

If you do this, the .ico files for these games are not downloaded, leading to a whole lot of desktop shortcuts without icons. They still work as you'd expect, but it looks a bit ugly.

The workaround for this is to download the relevant .ico files from steamdb and then place them in the <steamfolder>\Steam\games folder, but this is a bit of a hassle. I'd rather so that Steam would be more pro-active in downloading the relevant .ico files.