OP_RETURN was non-standard until 2014 meaning you literally had to mine the OP_RETURN output you create to get it on chain. They made OP_RETURN standard in Core version 0.9.0. There were OP_RETURN outputs prior but those were never relayed through Gossip.