If a newly created Office 365 user account does not appear in pm box user search the most likely reason is that SharePoint search hasn't crawled and collected that users' data yet.

SharePoint online search crawler run frequency is set by Microsoft and cannot be changed nor can a search crawl be triggered on demand. For more information, please refer to this Microsoft article

In some cases, it may take a few hours before newly added users show up in pm box (and SharePoint) searches.