Sync lost between AD and Office 365 for some users

Hi everyone,

We have been using Office 365, synced with our AD for a while and everything was working well, untill I move a few users from their OU to a new one.

Then those users ended up being deleted on Office 365. I found them in "deleted users" (not sure of the title in English, we are on a French version).
I then restored those users and I had to set a new password for each of them.

The problem is those few users are no longer synced with our AD.

The other users are still displayed as "synchronized with AD", as they all have always been, but those few users are now displayed as "In the Cloud".
They obviously still exist in our AD and they are also back as Office 365 users (with their mailbox and so on), but their two accounts are no longer synced with each other.
They also were removed from distribution groups (which are synced with our AD as well) on Office 365 and I cannot put them back in those groups, because of the sync issue.
Would you have any idea to fix this?
Thank you very much in advance for your help