From the statement no. 3 you have given, it shows no clarity wether you deleted or disabled the AD user as both are different.
First case:
If the AD user is deleted in AD then you need to check it if the same user is present in local that is in /etc/passwd file or the user might be getting logged in from some where else.
Run #getent passwd <userid>
For a deleted user id above command should not return anything.
Example:
[root@linuxserver ~]# getent passwd test
test:*:1192:503:test:/QA/test:/bin/bash
If getent on the deleted user id returns his configuration means you didn't deleted it properly or user id is present locally on server. So make sure that it is deleted in both/all the places.
Second case:
If the AD user is disabled in AD but not deleted:
Then you need to check your PAM settings in sshd configuration file, PAM modules, ad_gpo_access_control settings in sssd.conf file.
Two step solution for all the cases (No need to check in all 100 servers):
Make sure that same user id is not present locally on ubuntu server
Go to Active Directory server -> open AD -> go to users -> search and select user id -> click on properties of user id -> go to attribute editor -> go to login shell -> change the login shell to /bin/false