Changing MX record from Mail Relay to Exchange Server

This may be an absolutely dimwitted question to some, but I have no idea.  I need a quick answer badly, so I'm offering 500 points:

My company used a seperate server as a mail relay machine with anti-spam software on it.  So, as e-mail came into the company, it was sent through the mail relay before it got to the user to check for spam.  Well, that server went belly up, and I didn't think it was the best practice anyway, so I took it out of the loop and am now attempting to set up my Exchange Server (2000) to handle all e-mail without the mail relay machine.  I've been told from some research that I need to change the MX record in DNS, but unfortunately, there were two MX records in DNS, one for the Mail Relay and one for the Exchange Server.  I deleted the Mail Relay record and changed the priority on the Exchange Server to the same that the Mail Relay had before, I've cleared the DNS cache, but so far there's been no mail deliveries.

Please help me figure out to get outside mail flowing into my company again without the aide of a mail relay server.