First, as a preventative measure, Microsoft recommends taking steps to prevent administrators from being able to delete objects in bulk. They recommend using the ADSIEdit, LDP or DSACLS command-line tools to set the access control entry (ACE) to "deny" on the security descriptor of every object and its parent.
Barring that, Microsoft recommends three ways to restore deleted users. The first is to restore the accounts using the Ntdsutil command-line tool, which is only available on Microsoft Windows Server 2003 with Service Pack 1, and then adding them to their groups. The second, without the tool, is to use the most current system state backup of the global catalogue in the user's domain controller. This of course, has to be done before the current global catalogue has replicated and overwritten the backup.
The third method is to restore both the deleted user and his or her security groups twice. Microsoft says the process has to be repeated to repair group membership information, which may not be fully restored in one go around.
There are also other manual restoration methods in the Microsoft Knowledge Base at KB 840001. The article is an excellent reference with details and step-by-step instructions on how to restore Active Directory accounts.
This was first published in February 2009