To disable a user in Dynamics 365 online, we can remove their Dynamics 365 licences on Office Admin Centre. However, we recently had an issue where we removed all the licences for a user that included Dynamics 365 in Product licenses list and yet the user was still enabled in Dynamics 365 instances.
Upon doing some research we found that as part of the expansion of the Common Data Service, it now contains Dynamics 365 Customer Engagement platform too. Therefore, we had to remove the Common Data Service licence off the users too.
Removing both Dynamics 365 licences and Common Data Service licence from the user solved the issue. The users were no longer enabled in Dynamics 365.