In my "Services" I have some services which points to non existing exe files and directoies.
It would be nice if it could clean those invalid entries too
Since CCleaner doesn't have that ability I'd recommend looking into HijackThis, which can remove services via the 'Misc Tools section'. Just make sure you make a System Restore point before removing them though!