have you tried any of the following
check eventvwr [directory services] for errors
The following command will show you inconsistencies between 2 DC's
dsastat /s:server1;server2 /b:dc=domain,dc=com /gcattrs:all /sort:true /t:false
The following command will show you inconsistencies between OU's on the DC's
dsastat /s:server1;server2 /b

u=the_ou,dc=domain,dc-com /gcattrs:all /sort:true /t:false /p:20 > c:\dsastat.txt
Just a table to let you know what all that means
/s = server
/b = base distinguished object
/gcattrs = Global Catalog Attributes [acronyms who would guess]
/sort = duh
/t:false = full content comparison
/t:true = count objects
/p = number of pages
> c:\dsastat.txt = export to text file, easier to read
repadmin /showrepl servername = to show who replication partners are
repadmin /showutdvec serverName dc=domain,dc=com
e.g make a change, then run on second server and check the USN have been updated. If not try the commands below to force replication
repadmin /showconn servername = you can check for failures
repadmin /replicate server1 server2 dc=domain, dc-com
= destination = server1, source = server2
repadmin /syncall /A /e /P = replicate to all partners case sensitive /A = all /e across sites /P = Push replication
repelmon = this can do all the above through GUI
e.g check replication topology = causes KCC to rebuild.
sync each dir = same as /A /e /P command
Check dssite.msc If all failed. You can delete connections. Then right click NTDS - > All Tasks -> Check Replication Topology, will automatically rebuild the connections
The only way I know how to make users reappear is Authoritative restore or 3rd party apps. And after 60 days [tombstone] they should not be able to be retored.