When you delete something, it does indeed remain on your HD, but the space it used is marked as free. This space will then get used whenever the OS requires it. Therefore, I'm not sure how a 'deep cleaning' program could free up loads of space, as in practice, it's already free.
Some space can be gained (though usually not a lot) by removing files previously uninstalled programmes left behind, which are now not needed. I used to use a program called WinOptimizer (for Windows) to do this - I think you may have to pay to use it now though
. However, you were talking about freeing up space from deleted files - this is different, as these files still reside on your system, having never been deleted.
The only other thing I can think of is file shredding, where traces of deleted data are removed from the HD by repeatedly writing random bits over them. Again, this will free up no extra HD space (though, if you are bothered about security, you should do this before you ever sell your computer or HD, just to remove the slight possibility of someone finding your old personal data/passwords etc - just formatting the drive actually leaves all the data on it!!).
Hope the helps.
