i think the know the use-case would be relevant to choose the way to store the message: OP_RETURN is for sure the cleanest/most elegant way, however it's prunable (https://en.bitcoin.it/wiki/OP_RETURN)... so imho it should be evaluated if its presence guaranteed only in full nodes is ok or not