SMTP Protocol Returned a Permanent Error 554 Relay

Our company was 2 companies but sharing one mail server, everyone was on notes. Today we migrated about 1/2 the users over to Exchange, so we now have our companies split up.

The problem we have is that when we email from notes to exchange, both are in the same activeX domain and inside the firewall, we get an error:

SMTP Protocol Returned a Permanent Error 554 Relay rejected for policy reasons

There are no references to our 2nd company in the notes world, but for some reason it will not let the email out. We have tried multiple things to get it to work, but nothing has seemed to work (ie direct connection, smtp connect).

Any ideas what is causing this?

TIA