It was a little unclear to start, but I understand exactly what you are saying. Your not doing any thing wrong, your just not doing a little more work to set exchange up correctly.
I understand you have exchange 2000 setup with an internal domain Ex. InternalDomain.com, and you have an external Domain Ex. ExternalDomain.com. Your users are already setup as user@internaldomain.com, but you want them to use user@externaldomain.com. You need to update what is called "Recipient Update Policy" This is a query that tells exchange what internet domain names to give users. Open up Exchange System Manager on the server. Go to recipients, recipients policy, and right click "default policy." Under the email tab, click new, and add a new smtpdomain for the externaldomain.com you registered. Highlight it and select "set as primary" now close the properties, right click the default policy again, and "click apply this policy now" for it to propogate to all clients.