When the Kerberos elevation of privilege (CVE-2014-6324 / MS14-068) vulnerability has been made public, the remediation paragraph of the following blog post made some waves:
http://blogs.technet.com/b/srd/archive/2014/11/18/additional-information-about-cve-2014-6324.aspx

"The only way a domain compromise can be remediated with a high level of certainty is a complete rebuild of the domain."

Personally, I agree with this, but .... But whether this is the real solution, I'm not sure. And the same applies to compromised computers. When it has been identified that malware was able to run on the computer (e.g. scheduled scan found the malware), there is no easy way to determine with 100% certainty that there is no rootkit on the computer. Thus rebuilding the computer might be a good thing to consider. For paranoids, use new hardware ;)

But rebuilding a single workstation and rebuilding a whole domain is not on the same complexity level. Rebuilding a domain can take weeks or months (or years, which will never happen, as the business will close before that).

There are countless documented methods to backdoor a computer, but I have never seen a post where someone collects all the methods to backdoor a domain. In the following, I will refer to domain admin, but in reality, I mean Domain Admins, Enterprise Admins, and Schema Admins.

Ways to backdoor a domain

So here you go, an incomplete list to backdoor a domain:

• Create a new domain admin user. Easy to do, easy to detect, easy to remediate
• Dump password hashes. The attacker can either crack those or just pass-the-hash. Since KB2871997, pass-the-hash might be trickier (https://technet.microsoft.com/library/security/2871997), but not impossible. Easy to do, hard to detect, hard to remediate - just think about service user passwords. And during remediation, consider all passwords compromised, even strong ones.
• Logon scripts - modify the logon scripts and add something malicious in it. Almost anything detailed in this post can be added :D
• Use an already available account, and add domain admin privileges to that. Reset its password. Mess with current group memberships - e.g. http://www.exploit-db.com/papers/17167/
• Backdoor any workstation where domain admins login. While remediating workstations, don't forget to clean the roaming profile. The type of backdoor can use different forms: malware, local admin, password (hidden admin with 500 RID), sticky keys, etc.
• Backdoor any domain controller server. For advanced attacks, see Skeleton keys 
• Backdoor files on network shares which are commonly used by domain admins by adding malware to commonly used executables - Backdoor factory
• Change ownership/permissions on AD partitions - if you have particular details on how to do this specifically, please comment
• Create a new domain user. Hide admin privileges with SID history. Easy to do, hard to detect, easy to remediate - check Mimikatz experimental for addsid
• Golden tickets - easy to do, hard to detect, medium remediation
• Silver tickets - easy to do, hard to detect, medium/hard remediation
• Backdoor workstations/servers via group policy
• HKEY_LOCAL_MACHINE\ Software\ Microsoft\ Windows\ CurrentVersion\ RunOnce,
• scheduled tasks (run task 2 years later),
• sticky-keys with debug
• Backdoor patch management tool, see slides here

• Assign SeEnableDelegationPrivilege to a user 
• Directory Service Restore Mode (DSRM)
• Malicious Security Support Provider (SSP)
• DSRMv2
• AdminSDHolder
• Edit GPO 

Other tricks

The following list does not fit in the previous "instant admin" tips, but still, it can make the attackers life easier if their primary foothold has been disabled:

• Backdoor recent backups - and when the backdoor is needed, destroy the files, so the files will be restored from the backdoored backup
• Backdoor the Exchange server - get a copy of emails
• Backdoor workstation/server golden image
• Change permission of logon scripts to allow modification later
• Place malicious symlinks to file shares, collect hashes via SMB auth tries on specified IP address, grab password hashes later
• Backdoor remote admin management e.g. HP iLO - e.g. create new user or steal current password
• Backdoor files e.g. on shares to use in SMB relay
• Backdoor source code of in-house-developed software
• Use any type of sniffed or reused passwords in new attacks, e.g. network admin, firewall admin, VPN admin, AV admin, etc.
• Change the content of the proxy pac file (change browser configuration if necessary), including special exception(s) for a chosen domain(s)  to use proxy on malicious IP. Redirect the traffic, enforce authentication, grab password hashes, ???, profit.
• Create high privileged users in applications running with high privileges, e.g. MSSQL, Tomcat, and own the machine, impersonate users, grab their credentials, etc. The typical pentest path made easy.
• Remove patches from servers, change patch policy not to install those patches.
• Steal Windows root/intermediate CA keys
• Weaken AD security by changing group policy (e.g. re-enabling LM-hashes)

Update [2015-09-27]: I found this great presentation from Jakob Heidelberg. It mentions (at least) the following techniques, it is worth to check these:

• Microsoft Local Administrator Password Solution
• Enroll virtual smart card certificates for domain admins

Forensics

Lessons learned

But guess what, not all of these problems are solved by rebuilding the AD. One has to rebuild all the computers from scratch as well. Which seems quite impossible. When someone is creating a new AD, it is impossible not to migrate some configuration/data/files from the old domain. And whenever this happens, there is a risk that the new AD will be backdoored as well.

Ok, we are doomed, but what can we do? I recommend proper log analysis, analyze trends, and detect strange patterns in your network. Better spend money on these, than on the domain rebuild. And when you find something, do a proper incident response. And good luck!

Ps: Thanks to Andrew, EQ, and Tileo for adding new ideas to this post.

Check out the host backdooring post as well! :)