By External Addresses, do you mean SMTP/MAPI? If SMTP, check to see if you have a corporate virus scanner which blocks port 25 (the default for SMTP notifications)
Did test notifications work at all?
If you are trying to use Netsend to external computers, verify that the Messenger service is turned on at both machines, sender and receiver. In W2K3, MS turned this service off by default.