You can create a Recipient Policy based on group membership, and make all CompanyA users member of a CompanyA group and all CompanyB users member of a CompanyB group.
Here’s how:

Create a new recipient policy, make it a Custom Search, select the Advanced tab and enter your query like
(&(memberOf=CN=companya.users,OU=Service,DC=companya,DC=com))

Set the email address accordingly (ie %d@companya.com)

Go to the Service/CompanyA/com OU and create a group named companyausers.

Create your users and before you mail enable them, make them members of the companyausers group.

Mail enable your CompanyA users and they will get an email address from the Recipient policy you just created.