Mail Issues - Why mails got returned

I agree with Simon, adding a DKIM record make no sense.  So go to the web sites that he has listed and put in your domain name.

Failed e-mail delivery has nothing to do with what client (Outlook, webmail, Thunderbird, or something else) you use.

Thank you very much, everyone.  One thing I am sure that they have messed up, but they don't want to admit.

After more than 80 hours since the first ticket being initiated to them, it was still not working.  So I wrote another email to question about the status.  I thought they would say I need to wait for another 24 hours because the A record was created 1 day after they replied to my 1st ticket.  Technically I should wait for 72 hours after the 2nd ticket, total 72+24= 96 hours. In another words, I should wait for another 16 hours before the max waiting time is reached.

To my surprise, they came back unbelievable quick saying they had a look and now all fixed up.  My domain works, emails via outlook work, emails via webmail (through the hosting account) work.  I am not sure what they are really doing.  

One thing I'd like to mention.  The domain I didn't use much previously.  It is just a domain, no website developed for a few years.  Recently I develop a website.  In addition,  the emails I received got more serious stuff.  I mean got client enquiries, etc.   I am always wondering how secure the emails are hosted by a hosting company.

Do you think you can give me an idea of what actually really happened?

Hi,

Thank you very much.  A few best solutions.  As Simon was the first one to reply and provided a few URLs to read, so I picked up his.  I am  confused with A record, MX record.  When I find time, will spend some time studying it.  At the moment, seems work fine.

Thank you again. My apology for late feedback.