Bem, eu tenho uma solução, mas não vejo como o problema poderia ter surgido, exceto por um instalador com bugs no skype.
msconfig estava listando o comando para executar como: -
"C:\Program Files\Skype\Phone\Skype.exe" /nosplash /minimized
Observe a barra dupla lá antes de Phone
!
Alterar a entrada do registro para HKCU\Software\Microsoft\Windows\CurrentVersion\Run\Skype
para remover a barra extra corrigiu o problema.