I've solved the mystery. The problem:

1. User. I was using an administrator account to view which could access everything. Make sure if you are trying to setup security rights, you create an admin account for each company.

2. Parent Company settings. I configured it such that company A was the parent of company B. 

With these 2 settings, the company's contacts were invisible to each other. 

Hi,

make sure that the 'company' field (the tab 'Sales & Purchases') is not empty for a definite partner. If so, a contact is considered as global, thus, available for any company.

Take into account also that some models do not have multi company rule. Usually it some sort of classifier as, for example, product category.