IF you have already verified the domains in the tenant, check in Exchange Online to be sure they are listed as accepted domains. If they are not - you may need to contact MS support as they may need to run a back-end sync job for you.
If both verified and accepted domains are correct and your still not seeing objects, I would recommend you pick a few test objects, and first ask Microsoft to still do the back end sync and give them the objects. If that works you can let them know you need it done for all objects in the tenant. If that doesn't work then you may need to "Jiggle" the sync operation entirely.
Move those initially selected objects to an OU that is NOT syncing. Run a sync, and this should result in object being removed from the Azure AD database. Also be aware this will put your user object in Office 365 in a deleted state temporarily. Validate you can no longer find the object by opening the Synchronization Service application and clicking the Metaverse. Search for one of the objects we removed, it should return 0 results. If the objects are still there run another sync.
Once the object is no longer in the database, and you have also confirmed the account is not an active account in Tenant, you can move the users back to the original OU and then sync them again. In Office 365 check the user object and validate all data has synced. If this works, you can run thru your existing objects and complete this process and get things working as expected again.
If you run through this and the object is never removed from the Metaverse database, you need to install a new instance of Azure AD Sync.
I've had to go thru this process for numerous attributes that for whatever reason fall "Out of sync". While it's rare - it does on occasion affect an entire object type like "users" or "groups".