Here's an example of what Modifying the recipient policy will do for you:
You have an Active Directory, MyAD.local. When you install Exchange, you will get a default address space of @MyAD.local.
You also own MyCompany.com and you want to receive email for that domain. You add @MyCompany.com to the recipeint policy. Users in the domain should automatically update with the additional SMTP address. You can now send and receive for you external domain.
Now... If you're trying to receive for @hotmail.com, what the heck is the reason for that? You should own the address space you are going to receive for, and you should have MX records set up on the internet to allow resolution to your domain. Maybe I'm not understanding?
And based on the last message:
Final-Recipient: rfc822;account@company.com
Action: failed
Status: 5.0.0
That message usually comes across if you don't have an MX record, or you don't have a public IP for your server. It suggests that the mail system you were sending from attempted to connect, but couldn't find the server it needed to talk to.
You actually don't need to set up a static NAT on your firewall for exchange to send mail outbound. As long as it can reach the internet and perform a DNS lookup, it will send. So you may have both an MX and firewall issue in addition to the recipient policy.
PSC