Are you testing with the same two email accounts? If not, to avoid possible issues from different email accounts, please try using the same two email accounts to test and see if the issue has any difference.
I did some research about sending encrypted messages with AIP and your error prompts. First of all, it is suggested for you to check the steps of encrypting Outlook messages in this article and see if you have operated properly. (Note: Since the web site is not hosted by Microsoft, the link may change without notice. Microsoft does not guarantee the accuracy of this information.)
Besides, are there multiple email accounts in your Outlook client? In order to avoid confusion between multiple accounts, it is suggested for you to add your email account to a new single Outlook profile via Control Panel > Mail > Show profile and see if your issue has any difference.
By the way, can this message be opened normally if you configure your Gmail account to your Outlook client? If so, I found this similar thread External users cannot open encrypted email, the discussion of the third party solution might could be helpful to you, please check it.
Any updates, please feel free to let me know.
If an Answer is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.