Here is my solution. I'm proud of it! I hope this is the best solution for this problem.

We already had this new field on the res.partner model :

partner_territory = fields.Many2one('res.territory', string='Partner\'s territory')

We also already had this new field on the res.users model :

user_of_territory_ids = fields.Many2many('res.territory', 'res_territory_users_rel', 'user_id', 'territory_id', string='Allowed Territories for this user')

 We added this new field on res.territory. This field is the inverse (don't know if it is an acceptable term...) of user_of_territory_ids on res.users. This new user_ids field use the same table of user_of_territory_ids on res.users.

user_ids = fields.Many2many('res.users', 'res_territory_users_rel', 'territory_id', 'user_id', string='Users who have this territory allowed', readonly=True)

And we override the base.action_partner_form with this new domain.

<record id="base.action_partner_form" model="ir.actions.act_window">
    <field name="domain">[ (  'partner_territory.user_ids','in', uid  )  ]</field>
</record>

Once again, it is like magic! Good! Good!