When trying to do a redirect on a mailbox externally, it was not processing the email.
Internal was fine.
Apparently forwarding / redirects to external domain names is disabled by default in Exchange 2007 and 2010.
To change this setting, open the Exchange Management Console, and drill down to the Organization Configuration -> Hub Transport. Under the Remote Domains tab, open the Default domain.
Then, on the format tab, check the “Allow automatic forward” box.
Alternatively, from the Exchange Management Shell (PowerShell rocks!), this will do the trick:
set-remotedomain -identity Default -AutoForwardEnabled $true