First, the most important goal of a fired sysadmin is to clean up his past, particularly if it was a departure in bad standing. If an attack on his previous system were to happen he wouldn't stand to gain anything (particularly not his old job), but he could lose a lot. I've been faced with similar fears many times, but in my opinion, they are largely unfounded. I think it is way more likely that if you were to pose him some questions, he would be very nice and helpful to you (which you should then in turn mention to your boss).
Now consider the very unlikely case, that he really wants to do something harmful.
Make an archive of your whole network into some - for him - unreachable location (behind a firewall out of his responsibility, hard disk in a locked cabinet, etc).
As soon as you've made this backup, he can't cover his tracks any more. In the case of a rogue attack, it will serve as evidence.
You can't ever be 100% sure (except in the case of a reinstallation of the whole network). You can pass through a checklist, but you can't ever be sure that you've checked everything.
Even in the case that you find a hole, you can't prove that it was placed there intentionally. Note, the same problem exists for software developers. Bad work is not a criminal offense, and you can't prove that he "forgot", for example, to change the default database admin password, intentionally. Or that users, whose password was set by him, "accidentally" were granted the privileges required to connect to your top-secret databases.
In most cases, the most important part of your system isn't your OSes, but the data which is managed on them. It is particularly so, if this data is private data and the property of your customers. He could have stolen them long before his last workday, encrypted them and saved them in places known only to him. So make sure to also check for traces that indicate that he made copies of your data before he left. Note though that if he did it "properly", you won't find anything.