Just some extra info to kens post. I've just updated Skype, and it does have an entry in Tools/Options to have Skype start with Windows.
I've just tried setting that and rebooting, and Skype
does put an entry into the Startup registered by CCleaner. It also starts a service running called Skype.exe.
Have a look in Start/Run enter "services.msc" (without the quotes) and hit OK or Return, and see if there's a Skype service running. If so, you can disable it, or set it to manual, which is probably better, by selecting "properties", and set the startup type.
Even logging off Skype without closing the program down properly still doesn't have it starting again with windows. I can't reproduce what's happening on your PC. I run XP as opposed to your Vista, but I don't think that would make any difference here. If it does, someone will surely tell me.
Try that useful Utility program ken links to, and check out "services".
Hope this helps.