This is either a problem of your DNS manager (whoever supplies the control panel) not having propagated the settings to the internet yet, or there's a misunderstanding on your end about what records need to exist.
To have a proper DNS environment for mail, you need two records.
1) You need an A-record for your mailhost. It maps a name to an IP: mail.xxxxxx.com A 45.36.27.86
2) You need an MX-record that maps the domain to the A-record you created and gives it a priority: mail.xxxxx.com MX xxxxxxx.com 10
Do you have both of those? If so, then it's an issue with your DNS manager pushing those records out. It may just be a matter of waiting, if you haven't waited 12-24 hours since making the change. The way to test immediately is to run NSLOOKUP:
From the command-line: NSLOOKUP
set type=MX
xxxxxx.com
(retry several times if you don't get results at first. If the result is wrong, or doesn't include the settings you just made, continue. Otherwise, you're finished, since this just verified that things are ready.)
set type=SOA
xxxxxx.com
(notice the primary name server in the results. You are going to use that name to make direct DNS queries with)
server nameofnameserveryoujustread
set type=MX
xxxxxx.com
Now if this is just a propagation issue, the last command you entered should show you the proper information about your MX record. You've gone straight to the source instead of waiting for propagation, and asked for the MX. If it doesn't give you the right answer, contact the people that built the DNS control panel and ask them what to do next.
ShackDaddy
Shackelford Consulting