Recently we faced with interesting issue in Sharepoint Online: for some parts of the intranet unique permissions were used. And for these securable objects we used special Sharepoint “group” (which is actually not real Sharepoint group) – Everyone except external users. One the same securable objects there were also permissions assigned to normal Sharepoint groups. After some time without any actions from our side permissions assigned to “Everyone except external users” group disappeared, but permissions assigned to normal Sharepoint groups not.
For now we solved it by using new Sharepoint group which has other AD group which in turn has all users in organizations and new employees are added there automatically (fortunately customer’s administrator had this group), but anyway this is quite interesting problem. So if you will face with the same issue or will find reason of this behavior please share it in comments.