For this customer, he had 69,000 Users but only displaying 50,000 when searching.
This view is obeying the 'report-like' limit of the results to be able to see resources that are been searched.
The Default value is 50,000, and if the edited User will be after that limit - you'll not see it.
It always was like this, but the results are random in terms of "I can see or not", as the SQL queries may return rows in any order, what SQL server may see fastest.