PeoplePicker randomly showing users from different domains

This is about SharePoint 2016 on premise. Currently we have two Active Directories; CurrentDomain.com and NewDomain.com

Plan is to migrate everything from CurrentDomain.com to NewDomain.com and as a first step SharePoint has been migrated. So all users are on CurrentDomain.com while SharePoint is on NewDomain.com

All users who are on CurrentDomain.com, their account also exists on NewDomain.com but like I said right now they all are accessing SharePoint from CurrentDomain.com while SharePoint is on NewDomain.com

I have enabled PeoplePicker to pick people from both domains but it is showing weird behavior. For some users it shows both of their accounts from CurrentDomain.com and NewDomain.com, while for some users it only shows their account from CurrentDomain.com and for some it only shows from NewDomain.com

When I display result of following then it shows both domains (and IsForest is true) so that means PeoplePicker is working fine.

$wa.PeoplePickerSettings.SearchActiveDirectoryDomains

I checked logs and found that it seems to be working fine and when we search for some user, then it returns results from both domains. But people picker doesn't show both users like I explained above.

Here are the logs when I tried to search user "some.user"

SearchFromGC name = currentdomain.com. start ...
SearchFromGC query = (|(&(objectCategory=person)(|(anr=some.user*)(SamAccountName=some.user*.................
SearchFromGC name = currentdomain.com. returned. Result count = 1

SearchFromGC name = newdomain.com. start ...
SearchFromGC query = (|(&(objectCategory=person)(|(anr=some.user*)(SamAccountName=some.user*.................
SearchFromGC name = newdomain.com. returned. Result count = 1

In all of this, one really strange thing happened. I was trying to search user "another.user" and it was only showing result from NewDomain.com. But after about 30 minutes of so, when I searched same user in people picker, then it started showing this user from both domains. I didn't do anything but it automatically started working correctly.

How do I check as to why it is not showing users from both domains?