Are these messages sent from Exchange?
I ask because I’m familiar with this problem and 100% of the time I’ve seen it, Exchange was the sender and the culprit.
My guess is that it’s erroneously sending out an opaque reference to an internal data store via SMTP. In the cases where it’s been solved, the sender did something to fix it.