Why do I get DNS failure every time I go to a workstation and try to send out email through Outlook 2000?
You need to go into the TCP/IP properties on your Exchange Server (the one running Internet Mail Service) and specify the DNS server that you want it to use for name resolution.
Chances are you either don't have one specified or you have an incorrect one specified.
You don't indicate any other difficulties with Internet traffic (Web surfing, etc.) so I'm going to presume that your connection is good and that you otherwise have proper DNS settings.