How do I set up my Mx records and how do I create a reverse DNS record?

We have SBS 2003 and are hosting our own email on Exchange. The other day I purchased a hosting package from godaddy and as soon as the DNS change went into effect we stopped receiving email. I had called them ahead of time to specifically tell them that they will only host our web site and that they are not to touch our MX records. They obviously lied to me; they touched my MX records and now we are not receiving mail.

I've set up DNS before but haven't done it in a while so I need help. By the way, when I talk to godaddy support a supervisor finally got on the phone and told me that they do not issue "suggestions" (formerly know as support) on how to set up your DNS records even though godaddy is now our DNS host and domain name registrar.

Anyway, here is what I need to know:

I need to set up a reverse DNS entry to mail servers can verify that our mail server not a spammer..... right? Is the reverse DNS record I need to create a CNAME or A record?

Thanks.