how to add MX record into my DNS server?

We have a Windows 2000 server in the company, also with IMail server installed, so it acts as a mail server.
In the meantime, the mail server is also a proxy server, providing Internet connection to the whole LAN.
But it seems that the mail server doesn?t work constantly, sometimes people cannot send out mails.
I try to diagnose to find out the problem. Now it might be due to our above DNS server.
We have an important partner in UK. E-mail is the most important way for our communication. So in order to guarantee our mails can arrive in their mail system. I think it may be helpful to add the MX record of the UK Company into DNS of our own server.
In DOS command, I run nslookup set qt=mx, have found out the MX record. How can I add them to DNS of our server?