Nice update and responsive ISP by the sounds of it!
I seem to recall that its only a warning by postfix that reverse name doesn't match banner name - this should not on its own stop mail being delivered.
X-Postfix; Host or domain name not found. Name service error for name=smtp type=AAAA: Host not found.
Its possible, although I'm certain on this, that could be a dns related issue. Check your /etc/resolv.conf see what nameservers you are using?