Unable to send emails to a shared mailbox from an external source in Exchange 2007

Hello Experts,

I have a strange problem that I'm pulling my hair out over (and I don't have that much to spare :-) ).  We have an Exchange 2007 environment.  I have created a security group to access a shared mailbox and then created the shared mailbox using the following Powershell commands:


new-mailbox -name:'MyCompany Trade Confirmations' -OrganizationalUnit:'MyCompany.local/ExchangeResources' -database 'excms\sg2\mbsx2 -userprinciplename:'MyCompanytradeconfirmations@azasrs.gov' -shared

add-mailboxpermission 'MyCompany trade confirmations' -user:'mycompany trade confirmation permission group' -accessrights:fullaccess

ad-adpermission 'mycompany trade confirmations' -user:'mycompany trade confirmations permissions group' -extendedrights:send-as -accessrights:readproperty, writeproperty -properties:'personal information'

We have Exchange cache mode enabled, so the newly created shared mailbox is not showing up in Outlook yet.  However I can access it using OWA.

When I send an email from my Outlook to the new shared mailbox, the message is delivered as expected.

When I send a message from an external mailbox to the new shared mailbox, I get the following:

  mycompanytradeconfirmations@azasrs.gov on 5/20/2013 9:19 AM
  The destination server for this recipient could not be found in Domain Name Service (DNS). Please verify the email address and retry. If that fails, contact your administrator.
  <testcorp.com #5.4.1 smtp;550 5.4.1 mycompanytradeconfirmations@azasrs.gov: Recipient address rejected: Access Denied>

Any help on resolving this would be greatly appreciated.

Nick