What I would suggest is the following:
Set up user groups for each of the companies and set the users of that company to belong to that company user group, and only that company user group.
You'll have to give those company user groups access to the administrator login (global config) and also give them access to the "Special" Viewing Access Level so that they can see the admin menu.
Create Viewing Access Levels for each company and set the "User Groups Having Viewing Access" to each of those access levels to be just the user group for that company.
Set up top level categories, one for each company, and set the Access on that category to be the Viewing Access Level you set up for that company.
Go into the Permissions for each of those top level categories, and allow actions by the company user group who has that category and deny actions for other companies.
So for example:
For company C-one set up
User group: C1
Viewing Access Level: "C1Access", with User Group having viewing access "C1"
User: "c1user" with Assigned User Group "C1"
Top level Category: "CatC1" with Access set to "C1Access"
If you've already got other categories on the system you will need to set them so that the user groups of the companies don't have access to them.