BACKGROUND: MX (Mail Exchange) records are used to have mail delivered to users on your domain. It MUST have an MX record (not just an A record), primarily because people typically use an E-mail address with your domain name ("joe@example.com"), not a subdomain ("joe@mail.example.com").
When you send mail to someone, your mail typically goes from your E-mail client to an SMTP server. The SMTP server then checks for the MX record of the domain in the E-mail address. For example, with "joe@example.com", it would look for the MX record for example.com. If a user did have an E-mail address "joe@mail.example.com", the SMTP server would look for the MX record of "mail.example.com". The MX record is a domain name, so the SMTP server then gets the A record for that domain name, and connects to the mail server.
Each MX record has 2 pieces of information associated with it. The first is a number ("Preference" number), the second is the domain name of the mail server. If there are multiple MX records, the SMTP server will pick one based on the preference level (starting with the lowest preference number, working its way up). It's O.K. to have more than one MX record with the same preference.
An example would be "example.com MX 10 mail.example.com", "example.com MX 50 mail1.myisp.com", and "example.com MX 50 mail2.myisp.com". An SMTP server would first try mail.example.com, and if that wasn't reachable, it would try either mail1.myisp.com or mail2.myisp.com (normally, it should pick one of the two randomly, unless it has a better reason to pick one over the other, since the preferences are the same).
Most domains only have one set of MX records, the MX records for their domain (and not any subdomains). Your first step is to get those MX records. If you saved the information you got in Step 4a, you should already have a list of your MX records. If not, follow the instructions in step 4a ("Get a list of all your A records"), but look for "MX" records instead of "A" records.
[If you have MX records for more than one domain, such as "example.com" and "ihostforthem.example.com", you will need to repeat steps 5b and 5c once for every domain with MX records]
First, make sure that all the MX records for your domain point to a domain name (IE, "example.com MX 10 mail.example.com"). Next, make sure that all the mail server names from the MX records have a corresponding A record. You can check the A record as described in Step 4a. For example, if you have "example.com MX 10 mail.example.com", you must also have a record such as "mail.example.com A 10.11.12.15" (unless the mail server isn't in your domain, such as "example.com MX 10 mail.myisp.com" -- but if so, myisp.com must have an A record for mail.myisp.com).
Problem? Your MX records MUST NOT point to a CNAME record. For example, "example.com MX 10 mail.example.com" can not have a corresponding record "mail.example.com CNAME smtp.example.com".
Problem? Your MX records MUST NOT point to an IP address. If so, mail servers probably will not deliver mail to you!
Problem? Do NOT use wildcards (a "*" in a domain name) unless you are positive you know what you are doing. In most cases, they provide unexpected results [RFC1912 2.7].
Next, connect to every mail server listed here to make sure that they exist, are responding to SMTP requests, and accept mail addressed to your domain. Every mail server you have listed MUST either be one your control, or one that has given you permission to use them [RFC 1912 2.5]
To do this, use Telnet. For the "Host Name", enter the mail server name (for example, "mail.example.com"). For the Port, enter 25. A second or two later you should see a welcome message. Type "HELO" followed by the domain name of the computer you are using. For example, "HELO eagle.example.com". Then, after you get a response, type "MAIL FROM: my.email.address@example.com" (using your E-mail address on your mail server), and then "RCPT TO: my.email.address@example.com". Then, type "DATA", "Subject: Test", a blank line, "Test", and then ".". After the response, type QUIT. Make sure that you get a copy of this E-mail. If you do not (it could take some time if you are using a slow mailserver outside your domain as a backup), try it again (in case you made a mistake). If you don't get that second test message, you probably have a serious problem (you may get an E-mail back saying the message wasn't deliverable).
Problem? If you only have 1 MX record for your domain, you really ought to add a backup mail server. You don't have to, but it will make you look more professional, especially if your mail server isn't reachable for some reason.