We had a single Exchange server that forwarded outbound email to a smarthost. We've just added another Exchange...
server to our organization and moved some user mailboxes to it. Let's call this new server Server B, and our old server is Server A. Now users from Server B can send email to users on Server A and to Internet recipients, but they can't receive email from the Internet, nor can users from Server A send any mail to users on Server B.
For clarity, smarthosts are non-Exchange SMTP hosts. These can be behind your firewall on the same network as Exchange server. However, the most common use of SMTP hosts is between your internal/intranet firewall and your external/Internet firewall -- in a portion of the network called a perimeter network or a Demilitarized Zone (DMZ). In most such deployments, Exchange servers forward outbound Internet mail to such smarthosts in perimeter networks, which then route mail to appropriate destination SMTP servers on the Internet.
Most likely, you have a smarthost configured on Server A's default SMTP virtual server. When you do this, you're telling Exchange to deliver all mail for non-local recipients (recipients that do not reside on that server) to the smarthost. You also do not have any SMTP Connectors. This works without any issues when you have a single Exchange server.
When you add another Exchange server to the mix, things get complicated. By default, all Exchange 2000/2003 servers can deliver outbound mail directly when you do not have any SMTP Connectors configured. That explains why users on Server B can send mail to the Internet. Servers in the same Routing Group can also exchange mail directly without any configuration. This explains why users on Server B can send mail to recipients on Server A.
However, users on Server A cannot send mail to recipients on Server B -- the SMTP virtual server on Server A delivers all non-local mail -- including outbound Internet mail and mail for recipients on Server B -- to the smarthost. The smarthost does not know how to route mail to Server B.
To fix this, you need to remove the smarthost settings from the SMTP virtual server on Server A, and create a SMTP Connector for address space *. You can make Server A a bridgehead, or make both servers bridgeheads should you wish, and configure the smarthost on the Connector's settings. Once you do this, Server A will be able to send mail to recipients on Server B directly, and only direct mail for recipients not in your org to the smarthost.
This will also resolve your inbound Internet mail issue for users on Server B.