It's really, really, really hard. It requires a very complete audit. If you're very sure the old person left something behind that'll go boom, or require their re-hire because they're the only one who can put a fire out, then it's time to assume you've been rooted by a hostile party. Treat it like a group of hackers came in and stole stuff, and you have to clean up after their mess. Because that's what it is.
- Audit every account on every system to ensure it is associated with a specific entity.
- Accounts that seem associated to systems but no one can account for are to be mistrusted.
- Accounts that aren't associated with anything need to be purged (this needs to be done anyway, but it is especially important in this case)
- Change any and all passwords they might conceivably have come into contact with.
- This can be a real problem for utility accounts as those passwords tend to get hard-coded into things.
- If they were a helpdesk type responding to end-user calls, assume they have the password of anyone they assisted.
- If they had Enterprise Admin or Domain Admin to Active Directory, assume they grabbed a copy of the password hashes before they left. These can be cracked so fast now that a company-wide password change will need to be forced within days.
- If they had root access to any *nix boxes assume they walked off with the password hashes.
- Review all public-key SSH key usage to ensure their keys are purged, and audit if any private keys were exposed while you're at it.
- If they had access to any telecom gear, change any router/switch/gateway/PBX passwords. This can be a really royal pain as this can involve significant outages.
- Fully audit your perimeter security arrangements.
- Ensure all firewall holes trace to known authorized devices and ports.
- Ensure all remote access methods (VPN, SSH, BlackBerry, ActiveSync, Citrix, SMTP, IMAP, WebMail, whatever) have no extra authentication tacked on, and fully vet them for unauthorized access methods.
- Ensure remote WAN links trace to fully employed people, and verify it. Especially wireless connections. You don't want them walking off with a company paid cell-modem or smart-phone. Contact all such users to ensure they have the right device.
- Fully audit internal privileged-access arrangements. These are things like SSH/VNC/RDP/DRAC/iLO/IMPI access to servers that general users don't have, or any access to sensitive systems like payroll.
- Work with all external vendors and service providers to ensure contacts are correct.
- Ensure they are eliminated from all contact and service lists. This should be done anyway after any departure, but is extra-important now.
- Validate all contacts are legitimate and have correct contact information, this is to find ghosts that can be impersonated.
- Start hunting for logic bombs.
- Check all automation (task schedulers, cron jobs, UPS call-out lists, or anything that runs on a schedule or is event-triggered) for signs of evil. By "All" I mean all. Check every single crontab. Check every single automated action in your monitoring system, including the probes themselves. Check every single Windows Task Scheduler; even workstations. Unless you work for the government in a highly sensitive area you won't be able to afford "all", do as much as you can.
- Validate key system binaries on every server to ensure they are what they should be. This is tricky, especially on Windows, and nearly impossible to do retroactively on one-off systems.
- Start hunting for rootkits. By definition they're hard to find, but there are scanners for this.
Not easy in the least, not even remotely close. Justifying the expense of all of that can be really hard without definite proof that the now-ex admin was in fact evil. The entirety of the above is not even doable with company assets, which will require hiring security consultants to do some of this work.
If actual evil is detected, especially if the evil is in some kind of software, trained security professionals are the best to determine the breadth of the problem. This is also the point when a criminal case can start being built, and you really want people who are trained in handling evidence to be doing this analysis.