Blacklist , Mail delivery failed: returning message to sender

Question

Hi, I found my domain had blacklisted from gmail.  
https://mxtoolbox.com/Pro/domain/ears.tw/

If I use domain "ears.tw" mail account to send mail to any gmail, i will receive below message:
---------------------------------------------------------------------------------------------
This message was created automatically by mail delivery software.
A message that you sent could not be delivered to one or more of its
recipients. This is a permanent error. The following address(es) failed:
xxx@gmail.com
    host gmail-smtp-in.l.google.com [108.177.104.26]
    SMTP error from remote mail server after end of data:
    550-5.7.26 This message does not have authentication information or fails to
    550-5.7.26 pass authentication checks. To best protect our users from spam, the
    550-5.7.26 message has been blocked. Please visit
    550-5.7.26  https://support.google.com/mail/answer/81126#authentication for more
    550 5.7.26 information. x20si569099otq.222 - gsmtp
---------------------------------------------------------------------------------------------
I had request my hosting provider that said I need to add "ears.tw" to postmaster
https://postmaster.google.com/
then google will remove the blacklist for my domain , right ??? 
Actually, I had added my domain into postmaster for a few days, but it still on blacklist. 
It's a urgent issue, does anybody can help me ? thanks

Keith R (The Sweeper) · Accepted Answer

Your hosting provider doesn't understand Google's Postmaster Tools.  Have another look at the MX Toolbox results.  You have no SPF record for your domain along with other issues that will affect delivery.  Get the MX Toolbox results clean and you'll have better results.  Make sure that your SPF record authenticates the actual SMTP server(s) that you use to send messages.
Also, work through all the advice in that support article that is listed in the error message.

jp88 · Accepted Answer

then google will remove the blacklist for my domain , right ??? 
Not necessarily correct.
 
You need to publish a DMARC record and an SPF for your domain, might help.
'
Your domain is also on a spamming blacklist.  Although Google maintain their own lists, being on any spamming list certainly can't be helpful.
 
Changes can take up to 72 hours to filter through, and Google may throttle you for a while until your reputation is established.