Relevant Product: Exclaimer Cloud - Signatures for Office 365
If you recall an email that has been routed to Exclaimer Cloud to add a signature, you receive a Recall notice informing you that the email message failed to recall successfully (despite the email being unread in the recipient's Outlook mailbox).
Microsoft has confirmed that any emails routed via a connector are likely to fail to be recalled. This is because the SearchKey property, which is used to locate the email message, is modified during the routing process.
This is not unique to Exclaimer Cloud, but it affects any route or service utilizing connectors - according to Microsoft, this is behaviour by design. As a result, recall email messages cannot be guaranteed when emails are routed to Exclaimer Cloud.
Unfortunately, there is no workaround, and you'll need to raise this issue with Microsoft.