I am not sure if one or both of your servers have been blocked to outside mail. If you check on Microsoft's site, and do a search on external mail blocked, it does come up with several remedies. The remedie for Exchange 2000 is:
Configuring an SMTP Server in Internet Information Services
If you want to use an SMTP server in Internet Information Services (IIS) to send outbound e-mail messages from Windows SharePoint Services, you must configure the SMTP server to allow anonymous access and to allow e-mail messages to be relayed. Note that the SMTP server you use must have Internet access to be able to send messages to external e-mail addresses.
Note The SMTP service for IIS is not installed by default. If you want to use the SMTP service that comes with IIS and have not installed the SMTP service, or you do not see the default SMTP virtual server in IIS, you must install the SMTP service manually. For more information about installing, configuring, and managing the SMTP service, see the Help system for Internet Information Services (IIS) Manager.
To complete this procedure, you must be logged on as a member of the Administrators group on the local computer, or you must be logged on using an account that is both a member of the SharePoint administrators group and that has been granted permissions to administer IIS.
Configure an SMTP server in IIS for use with Windows SharePoint Services
1. Click Start, point to All Programs, point to Administrative Tools, and then click Internet Information Services (IIS) Manager.
2. Click the plus sign (+) next to the server name that contains the SMTP server you want to configure.
3. Right-click the SMTP virtual server you want to configure, and then click Properties.
4. On the Access tab, under Access control, click Authentication.
5. In the Authentication dialog box, under Select acceptable authentication methods for this resource, verify that Anonymous access is selected.
6. Click OK.
7. On the Access tab, under Relay restrictions, click Relay.
8. Under Select which computer may relay through this virtual server, select Only the list below.
9. Under Computers, click Add.
10. In the Computer dialog box, select Single computer, and then, in the IP address box, type the IP address for your front-end Web server or single server running Windows SharePoint Services.
11. Click OK to close the Computer dialog box.
12. Repeat steps 9 through 11 for any additional front-end Web servers in your server farm.
Note You do not need to add the IP addresses for the back-end database servers in your server farm.
13. Click OK to close the Relay Restrictions dialog box.
14. Click OK to close the Properties dialog box.