Hover over the text next to the checkbox in the Multi-Company configuration:

A Contact with a Company set can be seen by users who are allowed to access that Company.
A Contact without a Company set can be seen users who are allowed to access any Company.
To setup some Contacts that can be seen by users and others that can't:
1. Uncheck Common Contact Book in Multi-Company Settings:

2. For Contacts that are to be shared between Companies, set no Company. For Contacts that are not to be shared, set a Company. Administrator can see all Contacts:

3. User A can see only Contacts set with Company A, plus any Contacts with NO Company set:

4. User B can see only Contacts set with Company B, plus any Contacts with NO Company set:
