Lets say you have a user in AD. They get all sorts of rights granted over time. They also get access in a remote domain that trusts your domain, to resources.
Then they leave the company and you delete their object. The deleted object becomes a tombstone object, which is meant to preserve the SID in case you wish to 'undelete' them, sort of.
So what happens to the ACE's that had their SID in it? Within the domain, my guess is after the tombstone expires it will get cleaned up. Since after all, what is the point of preserving the SID if all references to it are already gone.
What happens to the ACE's in the remote trusting domain? How does it clear up orphaned SIDs in ACE's and whatnot?
Any ACL containing an ACE for a deleted user will display the orphaned SID instead of user name. This ACE will not be removed after the tombstone lifetime.
The ACE is, itself, and explicit reference to the SID. An orphaned SID's ACE will remain "forever" in the ACL unless removed.
Same situation as above. There is no automatic "clean-up" of which I am aware.
This "problem" is one of the many reasons for granting permissions/delegations per group rather than per user for most everything. When the users leaves the company, you delete their user object. Granting their replacement the same permissions throughout the domain is as simple as adding the new hire into the existing group.