We have one user whose Office 365 Message Encryption (OME) message sent to any gmail accounts bounce back with "your message to xyz@gmail.com couldn't be delivered. XYZ wasn't found at gmail.com".
That seems like a standard "recipient not found" NDR, it should have nothing to do with encryption. Make sure you are using the correct address, and you can always run a message trace to get some additional info just in case.
