Niestety nic to nie dało.
Zauważyłem też, że dzieje się to wtedy gdy po reinstalacji Windowsa zmieniam lokalizację folderu OneDrive. Domyślnie jest ona na dysku C: a ja mam ten folder na innym dysku.
W związku z tym, że folder "Pulpit" też trzymam w folderze "One Drive" dlatego przeniesienie go w inne miejsce skutkuje utratą tych ikon.