The recipient is valid.
So their server should accept the message, rather than saying "Recipient address rejected: Policy Rejection - Please try later" and returning a 4XX status. That said, they might be implementing "greylisting" here.
They claim that qmail is interpreting the message wrongly and drops the message.
Wrong. qmail still has the message, and will try again later. That's what "deferral" means.
I think you have to be more patient. Or you need to tell us why you say "giving up" in the Subject - do the messages stay undelivered for 7 days and then get returned to sender? If that's the case, the problem is definitely at the remote end, which is doing something other than greylisting, or their greylisting is not working.