Já tentaste ocultar os ícones do desktop e voltar a mostrá-los para ver se isso volta ao normal?
Já fiz isso! Eu já pensei se não terá sido um problema originado pelo TuneUP, mas já uso este software à muito anos e nunca me deu problemas!Mesmo assim desinstalei-o e o problema persiste!
Enfim, acho mesmo que nunca vou chegar a perceber este problema, mas levanta muita curiosidade!
Formata o pc que volta ao sítio (tentando antes um restauro de sistema). Isso foi um dll que por algum motivo se corrompeu!