Finally found the solution to this.
MS support had me run the following query on the <org>_MSCRM DB. (I was the one who decided to sort by FullName which gave me the solution)
select P.*, oo.Name as [Organization Name], tt.Name as [Team Name], bb.Name as [BusinessUnit Name], ss.FullName from SystemUserPrincipals P
left join BusinessUnitBase BB On bb.BusinessUnitId = p.PrincipalId
left join OrganizationBase OO On OO.OrganizationId = p.PrincipalId
left join TeamBase TT On TT.TeamId = p.PrincipalId
left join SystemUserBase SS On SS.SystemUserId = p.PrincipalId
order by FullName desc
What I found was that only enabled users I added through the CRM GUI had a record where the PrincipalId field was the same as the SystemUserId. All of the users I imported did not have a record.
I also noticed that disabled users did not have a record. So that led me to try disabling the users in question and re-enabling them. Running the query again showed that the imported users now had a record in this table with the PrincipalId = SystemUserId.
The Advanced Find issue is now resolved (I'm sure with a lot of other issues).
Not sure why MS took over a month to even run this query. In fact after their tech saw the results, they still wanted to research it and perhaps run some delete/update queries. I think someone in MS and the CRM team should have thought of this possible cause.
select P.*, oo.Name as [Organization Name], tt.Name as [Team Name], bb.Name as [BusinessUnit Name], ss.FullName from SystemUserPrincipals P
left join BusinessUnitBase BB On bb.BusinessUnitId = p.PrincipalId
left join OrganizationBase OO On OO.OrganizationId = p.PrincipalId
left join TeamBase TT On TT.TeamId = p.PrincipalId
left join SystemUserBase SS On SS.SystemUserId = p.PrincipalId
order by FullName desc
