I checked out the DNS settings on a DNS testing site and it said everything was in order.
I noticed that in the qmail log the email addresses I'm having problems with are listed with the qmail local handlers
It seems like qmail is trying to deliver to local mailboxes, but they only exist on the remote exchange server. Although I had no entry in /var/qmail/control/locals for the domain, I did have one in /var/qmail/control/virtualdomains. I deleted that, restarted qmail, and sent a test email, after which I checked the logs and see, as the final entry
starting delivery 1: msg 8407810 to remote email@example.com
I haven't seen that message yet, so hopefully the problem is solved. I will confirm with the client.