The actual recorded login error in the logs was this:
Error: 18456, Severity: 14, State: 11.
Login failed for user 'Dom\User'. Reason: Token-based server access validation failed with an infrastructure error. Check for previous errors.
Eventually I came upon some rather useful resources for this cryptic error, and took some of the existing scripts and rolled it into a new script that takes all the domain user logins, gets the binary SID stored in SQL, maps it to SDDL format, and pulls the equivalent Windows SID via xp_cmdshell and WMI. Then it compares, and outputs the mismatches. This script isn't particularly well tested but it seemed to go over reasonably well on 2005, 2008R2, 2012, and 2014 instances.
Once you find that you do have a SID mismatch, the unfortunate solution is dropping and recreating the login, whereupon you'll have to make sure all permissions and memberships are retained. Also, one thing I found is that even when there is a mismatch of a SID, it doesn't mean that user can't connect, necessarily. I've yet to fully understand the whole process, but if the user is getting 18456 login failures AND there is a mismatch of SIDs, recreating the login will likely resolve that issue.
Classic disclaimer, don't ever run code you find on the internet on your servers as it will likely truncate all your data, give your servers venereal disease, and contribute to Global Warming. So Caveat Emptor! Also, the SDDL formatting code was
USE masterGODECLARE @DomName VARCHAR(50);SET @DomName = 'YourDomainGoesHere';IF OBJECT_ID('tempdb..#LoginSIDs') IS NOT NULL DROP TABLE #LoginSIDs;CREATE TABLE #LoginSIDs(
SQLSDDLSID VARCHAR(200) NULL,
WinSDDLSID VARCHAR(200) NULL
);/* Get relevant logins and SQL SIDs */INSERT INTO #LoginSIDs (name, NTname, BinSID)SELECT
SUSER_SID(name)FROM master.sys.server_principalsWHERE [type] = 'U' /* currently omitting NT groups */AND name LIKE @DomName+'\%'ORDER BY name ASC;/* Cursor through each to get reformatted SQL SID and Windows level SID */DECLARE @LogName NVARCHAR(128), @BinSID VARBINARY(100);DECLARE sidcursor CURSOR FOR SELECT NTname, BinSID FROM #LoginSIDsOPEN sidcursor FETCH NEXT FROM sidcursor INTO @LogName, @BinSIDWHILE @@FETCH_STATUS = 0 BEGIN
/* Convert binary SID to SDDL format */
@i INT, @j INT, @val BINARY(4),
SELECT @StringSID = 'S-'
+CONVERT(VARCHAR, CONVERT(INT, CONVERT(VARBINARY, SUBSTRING(@BinSID, 1, 1))));
SELECT @StringSID = @StringSID+'-'
+CONVERT(VARCHAR, CONVERT(INT, CONVERT(VARBINARY, SUBSTRING(@BinSID, 3, 6))));
SET @j = 9;
SET @i = LEN(@BinSID);
WHILE @j < @i
SELECT @val = SUBSTRING(@BinSID, @j, 4);
SELECT @StringSID = @StringSID + '-'
+CONVERT(VARCHAR, CONVERT(BIGINT, CONVERT(VARBINARY, REVERSE(CONVERT(VARBINARY, @val)))));
SET @j = @j + 4;
/* Get Windows SID from WMI */
CREATE TABLE #cmdOutput (txt VARCHAR(255) NULL);
SET @WMIcmd = 'wmic useraccount where (name=''' + @LogName + ''' and domain='''+@DomName+''') get sid';
INSERT INTO #cmdOutput EXECUTE master..xp_cmdshell @WMIcmd;
SELECT @WinSID=REPLACE(txt,CHAR(13),'') FROM #cmdOutput WHERE txt LIKE 'S-%';
DROP TABLE #cmdOutput;
/* Update temp table */
SQLSDDLSID = @StringSID,
WinSDDLSID = @WinSID
WHERE NTname = @LogName;
FETCH NEXT FROM sidcursor INTO @LogName, @BinSIDEND
CLOSE sidcursorDEALLOCATE sidcursor
--SELECT * FROM #LoginSIDs;
/* Output mismatches */SELECT * FROM #LoginSIDs WHERE SQLSDDLSID <> WinSDDLSID;