---BEGIN MESSAGE---
Test message
---BEGIN ADDRESS---
3Nxe7AjWBZFoctcQLrnfYeRL9XQChpv3kB
---BEGIN SIGNATURE---
JEuiD5vTQs7Br7wzyEPQ+POH5/3tCyFCmKkP2vGB5QVBIP4v/Gd3gvmohL+m6ZinnQzVbNssZtRFiZQ6UTdd2vE=
---END MESSAGE---
This is very interesting. I have my Trezor wallet's master public key in a watch-only Electrum wallet, and I just tried to very the message with that, but it also failed.
I imagine the bitcoin development team has bigger fish to fry, but it would be nice to have signatures and verification standardized.
As I wrote in the OP, I think you need to manually tweak Electrum (see the link I provided), and creating a p2sh segwit wallet to be able to verify messages from p2sh addresses.
Basically, the only way to verify p2sh addy messages is Trezor.