If they're checking using SMTP's VRFY command then it's actually considered a best practice for the server to always reply with a 252 "cannot verify" since otherwise it can be used to fish for valid addresses.
It's sad that VERIFY is basically dead due to spam. In the olden days, you might have been able to use finger - but it's also dead for (among other) similar reasons.
The spam cat and mouse game leads to quite silly situations for benign actors.
For some mx's you might be able to designate some ips as trusted, and do real verify for those.