Anyway, uh, I work for the company that makes Exchange so I had a dig around. I found a dev spec for message recall in OWA and while the transport is proprietary, there's definitely an identifier in the recall message payload you could put in the SMTP headers too.
(I suspect the reason why they didn't is somewhere between "did the bare minimum for interop" and "if you want this to work properly, pay for Exchange")