Marc,
If your Administrative logs are set to detailed, then when a user is deleted from a domain, you would see something similar to this:
[2015.05.27] 14:59:55 PM [10.X.X.X][t5gouz][Domain : DOMAINNAME] Setting Removed by [USERNAME@DOMAINNAME (Domain Admin)] : Setting Name: User
[2015.05.27] [Item: DELETED_USERNAME]