Are the recipients members of a distribution list? Is the distribution list email address (the "@domain.com" part) in your recipient policy?
Same questions above if it is a mail enabled security group.
Here's a test that I would perform.
Telnet to your mail server port 25 and use the SMTP commands to send an email to the address in question. Use an outside email address for the mail from: field.
Once you submit the message, you can use Exchange System Manger | Tools | Message Tracking to track your email. It will show how far the email got.
*ensure message tracking is enabled prior*
If you don't see any email tracks for this particular email then perhaps you have an anti-virus product installed such as that runs on Exchange to monitor mail going to/from the information store. If so, is that blocking it?