I understand when you share your Contacts and Companies to your users and they cannot see the Companies you shared, right?
May I know if all users cannot see the shared companies or part of them? Can those affected users see other shared OCM companies from other people? So, we can know if the issue is related to you or those users.
If they cannot see all others' shared companies, please let them try as following:
Go to IE settings > General > Settings under Browsing history > Caches and databases > Delete cache files for the website "outlookapps.com". Then, restart Outlook 2016.