We had a mailbox size issue in the account which was sending the emails. We had gotten a ton of "Unreachable recipient" messages. I deleted all those, then it worked fine.