What's the best way to protect myself when an administrator leaves the company?

There are a couple of things you can do. First, never put a single person into an ACL, with the exception of a mail file. Everything should be based on groups. This rule also applies to server document fields and applications. Use a generic ID for agent signing, and not an administrator's ID. This prevents applications from malfunctioning when your terminate an administrator's ID file.

Never give ANYONE more than editor access to your Domino Directory. This includes administrators. Instead, create a generic "Domino Administrator" user who does have manager access to the Domino Directory. They key to this is that the ID will require multiple passwords, where no administrator has more than one password.

After that, your standard practices for terminating an employee should be sufficient. You do have standard practices for terminating an employees, dont' you? This includes things like terminating network IDs, remote access IDs, cancelling corporate charge cards, etc.