Currently Product Catalog's categorization is global (Common to all). The solution would be move the categorization fields to Product-Company Association table & there is already an enhancemnt request for the same. For CMDB, there is a plan in the next release to add company field to CIs. Iam not in decision-making position to make a statement as to when these enhancements will be delivered.
As Suresh mentioned, the solutions you are proposing are being considered for a future release. The tenancy information needs to be added to product catalog so that different tenants could have their private products or private categorizations. Similarly, reconciliation engine will also require to be tenant aware and your suggestion about adding company=company qualification to the rules is right if there are multiple tenants where this a high likelihood that Names can be conflicting across two tenants. Until we provide a complete solution in future, the suggestions you are proposing will allow CMDB to be tenant aware in PC and RE.