I have un-ticked the "Start Skype when I start Windows" option, terminated Skype, launched it and ticked it again. Since then it starts on its own. No idea what was wrong.
Well, sometimes it does start, sometimes it does not. Still no idea what was wrong or how to fix it.
The solution from http://superuser.com/questions/16220/skype-doesnt-auto-run-at-startup/18407#18407 has worked for me as well. To make things harder, SysInternals autoruns did not display the double backslash, only a single one, therefore I missed the problem when inspecting the issue with it. This time I have used regedit and the problem was obvious.