In this type of scenario we need to verify couple of things. From SharePoint online admin center navigate to user profile service, there try to find that user, if it is found there in the user profile directory, then there is no issue with the sync.
For details steps how to navigate to user profile in SharePoint online admin center, please refer the below article :
Manage user profiles in the SharePoint admin center
Second thing to look upon, add the problematic user directly to the user information list (SharePoint hidden list) and try to access the SharePoint site, at this point mostly user will not be able access the site, will get access denied error. Now, wait for few hours to run the synchronization job to run, in the next run it should be synchronized.
For all types of licenses, user profile service doesn't synchronize automatically in SharePoint online, in those scenarios, need synchronize manually.
Adding user using PowerShell is more effective than the from the UI in terms of synchronization.
Similar question is discussed in the below thread :