How widespread is OP_RETURN forwarding and mining (as of February 2014)?
It will take until bitcoind version 0.9 for wide spread support for relaying OP_RETURN.

Adding fees will not help. Currently, transactions with OP_RETURN are by default not relayed by the main net (last sentence):
https://en.bitcoin.it/wiki/Script#Provably_Unspendable.2FPrunable_Outputs

P2Pool seems to accept them, so that could be a solution for you: submit them to a P2Pool node.