SQL Server login not working
Check the SIDs of the accounts in SQL and AD before the SQL login deletion to confirm they are indeed the same and the AD admins didn't really delete and recreate the AD user account just telling you otherwise. 

Articles: http://sqlserver-help.com/2014/05/27/sql-internals-how-to-map-login-sid-to-domain-account/ and https://technet.microsoft.com/en-us/library/ff730940.aspx

There may be a way to get both from PowerShell but confirm what the AD domain and forest functional levels are and research with your version of SQL Server for known bugs -- maybe it's time to upgrade/update one or the other.