Based on our discussion, I was having the same problem but the problem was slightly different.
Why this is happening: When you a add new user to AD, the profile sync job takes some time to pick the newly added user and create the SP UPS entry, and which finally syncs with all site collections and creates entry in UIL. Until the UPS is not available, people picker wont show the user. Now when you add this user to AD groups which are mapped to SPO Groups, they gets the permission, and ensure user method will returns true as well, still people picker dont show the user, since the information is yet not available on UPS/UIL. In our case, we were using SPO so usually it takes b/w 1-4hours to create the UPS.
Solution we used on SPO: I created a SP Group (lets say Jump Start SP Group) on root site, which is having only limited read permissions. Ideally this SP group does nothing in regards to permission. Now once the new user is created, we add them directly to jump start group (we used Azure to automate the process). Doing this, force SP to create the UPS for the new user, and now the user is available in people picker.
Since we were using Identity Access Management tool we were able to automate this process. Now for on-prem, you might need to think a bit more on how to automate this process based on your environment setup and process. But simply adding use to site directly will solve people picker issue.