Booting from a CD can make a difference when using tools like chkrootkit or rkhunter to scan for changes because any intruder hasn't had a chance to tamper with them. Of course it is best if you either have a CD that was burned prior to the intrusion or burn a new one on a separate computer. However, since the CD boots from its own, untainted, kernel, any running exploits that might be picked up by nmap, lsof or netstat, are going to be gone.
If you reach the point where you're pretty sure you haven't been cracked, I'd strongly suggest setting up a file monitoring system. Aide, Tripwire and Samhain are three pretty popular monitors. As long as you keep a copy of their database off the system, you can always go back and scan from a trusted point and see exactly what files have been altered. You also might consider running Snort if you keep this attached to the internet all the time. Snort won't prevent any attacks, but it can help alert you when one happens.