Gubinz Answer:
I've used Ncleaner and CCleaner and they worked I suppose although I never saw any speed improvement. I have also seen Ncleaner blue screen my work PC every time it was run up.
My understanding is that they are less important these days since we moved from the 9x version of Windows to the ones based on NT. A large registry doesn't tend to slow down XP, Vista, or 7. Microsoft recommend using Pagedefrag instead to defrag the registry hives and page file:
http://technet.microsoft.com/en-us/sysinternals/bb897426.aspx The registry files and pagefile wont normally be defragged by the built in defrag tool because they already exclusively opened.
Pagedefrag might speed things up but it wont fix a corrupt registry.
To track down those rogue .dll entries that are missing at startup, try using Autoruns
http://technet.microsoft.com/en-gb/sysinternals/bb963902.aspx. It's a free MS Internals app that will show you EVERYTHING that runs at startup (far more info than MSConfig) and where each file is expected to be. You can then match the .dll name to the entry in Autoruns and either put the .dll back or disable the dll from running at startup.
Koops Answer:
No you don't need one and be careful as many have malware in them.