So far as I can tell, the problem was not with SSRS but rather with Exchange. The SSRS server was on a different (older) domain than the Exchange server. When the SSRS server was migrated to the newer domain, the problem stopped happening.

We had a related issue with select individuals never receiving emails with data driven subscriptions, and this also resolved with the domain change.