I'd avoid them. Sometimes they screw with the registry. There are tools that better those that Windows provides, such as CCleaner and MyDefrag. But generally, they're not recommended.
I would instead recommend that you back up everything on your active partition (C drive?) that you want to keep and just format and reinstall WIndows. That's the best way of solving all your OS problems.
I'd recommend that you download the drivers for your hardware, along with the install files for the programs you use and back those up too. That way, when you've got your clean install, getting yourself back up and running will take far less time.

It can be hard sorting through the junk that is advertised for people with no idea of how to use a computer, but I think disk cleaners are the best of the bunch. You'd be surprised how much they really clean up.

I don't know about MyDefrag, but I never had any problems with CCleaner on XP or Win 7. I use it every day. Only, I don't fix the ActiveX/COM issues. I don't know if they are really issues, so I leave them as they are.
By the way, are they safe to fix/delete on Win 7?

Ahahahahahaha good one

One major cause of speed problems--unless you have faulty hardware and/or have installed a metric ton of rubbish shareware that has somehow totally screwed up the registry--is too large a number of background programs. Many popular programs love adding background programs to your system; some make their presence known with tray icons, but most do not. These background programs are meant to periodically check for updates and/or help the program load faster when you need to launch it, but the difference they make is minimal and most of the time they do nothing but tie up resources, which is especially noticeable when starting or shutting down the system (although Vista and newer streamline this to a degree).
Some programs have a setting for disabling their background programs, but most do not. You can get rid of background programs with msconfig (Start>Run>msconfig on XP and earlier, or just type it into the search box on Vista and newer). Any background program that doesn't sound like it does something really crucial (antivirus, Synaptics trackpad, etc.) can be safely disabled. If you have turned off the Windows Sidebar uncheck that too. Even background programs for your video card, sound card and mouse typically serve no purpose besides providing tray icon functionality and/or periodically checking for updates.
For most systems you should be able to cull background programs down to just your security software, the Windows Sidebar (if you use it) and your trackpad (if using a laptop; some trackpad functions such as scrolling may not work correctly without the background programs, but if you don't use those functions anyway you might as well disable that too). Even if this only saves ~20 MB of RAM and a tiny sliver of your CPU power every bit helps, especially for gaming purposes.
Unfortunately the background programs you have manually removed will typically be added again when you reinstall or update those programs, so you may need to check it from time to time to make sure your system isn't sliding back into decay again.

I mean yeah, it's not a pretty thing and it shouldn't exist at all (Linux, OSX etc.) but I don't see why one should have to maintenance it at any form with "cleaners". Does it really give you a speed boost if you have one or two keys less in there? Maybe only thing would be to destroy some keys that start programs with windows, but you can do that without messing with registry. Most registry maintenances I've done have been when I've changed Windows version and wanted to keep my game installs that only want some stupid registry keys of install path and current version. Backup-restore on those specific keys has worked quite well.
I still want those sheer numbers to see if it really is worth the trouble and possibility to mix something up, as basic user cannot tell which registry key is redundant. Some wikipedia link to "Marginal performance benefit" part of the article. Seems to have some sources as well.

No i was laughing at the thought of software developers writing clean code that removes itself from the registry when the app is uninstalled

Well i tried speedboost today, things go a little bit faster now but not really the increase i was looking for. looks like i have to reformat the disk. i hate that, i hope i find my windows CD.

Pro tip: Find your windows CD BEFORE formatting.
Its rather embarassing to do it the other way

I leave them be unless I'm experiencing problems with them. I tend to notice the same issues repeatedly cropping up when I do fix them though. So it seems they're simply added back in when removed anyway. So while it doesn't seem like it would cause any problems to 'fix' them, it won't really solve much either.

Is this from personal experience?

Yup, formatted my net/download machine only to discover that I'd loaned my XP CD to a mate who'd lost his disc, stuck without that system for a few days. No great loss but I felt a bit of a dick (which at least filled in time)

Most of those tweak programs you can find are just snake oil. At best they won't do anything, and at worst they will actually reduce your performances. As the other said, don't think that a program will magically make your pc faster. Even some of the tweaks you can find on the net to improve performances can also enter this category. In some cases it is possible to disable some stuff that might give you an increase of performance but it will likely be minimal for a modern machine and not worth the hassle, and that's assuming you do not cripple some of the system's capabilities in the process. As a rule of thumb, it is better to disable only stuff you know you won't need or that may cause a security problem, and to use some tools to do basic maintenance on your computer once in a while. I'm not a fan of formatting every given time because you are likely to run into the same problem again after a while and have to waste time reinstalling, while some basic steps could allow you to keep a healthy system running for years.
Else here are a few tools I use and that you might want to consider using:
CCleaner: already given by others and it is indeed nice and safe to clean your computer with. I managed to reclaim 1,7 Gb of space on my ex-girlfriend's computer with it, all used in temp files. The registry cleaning feature is also nice but the problem is that the registry is so vast that it is like removing a drop from the ocean and won't likely change anything; still my thoughts on this is that it is fast to do it once in a while and relatively safe with this program so why the hell not?
ERUNT is an old favourite of mine and is composed of two tools: erunt, that allows you to easily backup and restore your registry, and ntregopt, which allows you to compress the registry without removing anything, mostly by rebuilding the whole thing in order to make a compact entity. From what I read, this should give better results than removing unneeded data from the registry, which might actually fragment it and reduce performances. Use it as part of you regular maintenance routine after you run CCleaner.
PageDefrag is another tool that will take care of your registry and some other files. What it does is defragment the files that can't be accessed by regular defragmenters, such as the pagefile or the registry, and thus completes them nicely. Running it at every boot is a bit overkill but it doesn't hurt to do it once in a while. You can also see if these files actually need to be defragmented before you launch the program.
MyDefgrag was also mentionned and is a good alternative to the default defragmenter. You might want to look at the tips section on the website to see how you should best defragment your drives. Even if it is made to be used daily, I believe that this is a bit overkill and defragmenting at least once a month, or maybe twice, should be sufficient.
Autoruns will allow you to edit the programs and processes that start with Windows and seems like a better alternative to msconfig. Generally speaking I hate software that installs some resident program, unless there is a very good reason for that, and starting Acrobat Reader faster doesn't seem to be a good reason to me. You might first want to disable these programs normaly, perhaps in their respective options menu, knowing that you can use this program as last resort. Be extra careful with what you are doing though, as you can easily screw up your system. Autoruns will nicely separate the different programs into different categories, allowing you to see if one might be more important that the other, but if you do not know what it does, do not touch it. You also have the option to simply disable the autostart, thus keeping the entry and not deleting it, allowing you to easily repair your mistake.
That should do it for now. And again just beware of websites that tell you to do this or that tweak on your OS to gain a lot of performance, because there is a lot of misinformation going on. One of the most (in)famous is the rules on how to set the size of the pagefile as some fraction of your installed memory. As I said, some tweaks may help you a bit in terms of performances or security, but others will just cripple you.

As others have stated, stay away from those speed enhancer programs, they're mostly bloat/spyware that won't do anything except for marketing research without your knowledge.
And on that note, what browser do you use?
If it's IE thats your problem right there. Do a format, and the first thing you do when you get windows booted is download and install firefox, and never touch IE again. Spyware, trojans, all that garbage is much easier to get if you're using Internet Exploder. Since switching to firefox I haven't needed any adware scanners or even an anti-virus, and I don't ever have problems.

Yeah i also use firefox,though i still have IE installed.