That must be that blockexplorer's feature that identifies Exchange addresses to be able to tag them.
Those data must be stored in their own server and not in any Bitcoin nodes.
BTW, Blockchain blockexplorer isn't affiliated with Bitcoin nor the blockchain of bitcoin.
If you want another idea aside from OP_RETURN, try this:
- Use a "Vanity Address" with the message that you want; e.g.: 1HBDbob
However, this will be computationally expensive since the longer the message, the harder it is to create a vanity address that starts with it.
In average hardware, you can only easily include a 6-character message to the address. (7 if you're lucky)
You can make vanity address using this tool: VanitySearch (Yet another address prefix finder)
Then send bitcoins to that address and spend it as input of the transaction to the recipient of the message.
Hopefully, the recipient will notice that the sender's address has a message.