Cleared recipient email address(s), still using old dns - email sent being rejected?

I have a client i regularly email to (Exchange), who recently switched mail hosting providers. they have new mx/autodisc rec's setup and is working for all but me, on thunderbird (i can send/rec to these same addresses for example in gmail fine). cleared cache, etc - seems to be a stored dns/pointer issue, that is going to their old mail servers?

Any help appreciated. Thanks