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 due to the way that 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 at this time and you'll need to raise this issue with Microsoft.