I'll restrict myself to trace-preserving CP-maps.
One can rewrite $\mathcal O=\sum_{k,l}o_k|k,l\rangle\langle k,l|$, where the $o_k$ are in decreasing order. The non-increasing condition $\langle\mathcal O\rangle$ corresponds then to an non-increasing condition on $k$.
Writing $\Gamma$ in terms of Kraus operators, one has
$\Gamma(\rho)=\sum_i B_i\rho B_i^*$ with $\sum_iB_iB_i^*=\mathbb1$.
The condition on $k$ given above is then translated into the following writing of the Kraus operators:
$$B_i=\sum_{\substack{k,l,k',l'\\k\le k'}}B_i^{klk'l'}|k,l\rangle\langle k',l'|.$$
Another way to say the same thing is the condition $B_i^{klk'l'}=0$ if $k>k'$.
Then, of course, the normalization condition imposes
$$ \sum_{\substack{i,k',l'//k\le k'}}\left|B_i^{klk'l'}\right|^2=1, \forall k,l.$$
If you apply the same reasoning with a non-increasing and non-decreasing condition, you find that $k$ has to be conserved, and this is then equivalent to the commutativity condition you give in your question. In the same way, this answer is not general: you have operations which preserve $\langle\mathcal O\rangle$ without commuting with $\mathcal O$.
This post has been migrated from (A51.SE)