I'd argue this response was insufficient. I've always been taught that a clean wipe is the response to your box being rooted.

At step 3 one should be thinking "I now know nothing about this box, what's installed? What's modified?" You can't know if its been modified or rooted.

While I'm certain its possible to replace software in the system piece by piece until you trust it again, but that's much harder than what I would say is your only option:

Wipe the disk, put a a new install on it and restore your sites from backups.