A structural proof that $ax=xa$ forms a monoid During the discussion on this problem I found the following simple observation:

If $M$ is a monoid and $a \in M$ then $\{x: ax = xa\}$ is a submonoid.

This is trivial to prove by checking identity and closure under multiplication. Is there a more structural/conceptual proof, for example one that introduces some ideal, a homomorphism etc.? I attempted to use the monoid algebra $\mathbb{Z}[M]$ or a monoid action $a,(x,y) \to (ax,ya)$, but couldn't formalize it.
 A: I don't know whether to call the following a "structural proof" or a "fancied-up proof."  In any case, it's different from the obvious proof.
Let $R$ be a ring.  An additive function $d \colon R \to R$ is called a derivation if $d(xy) = d(x)y + xd(y)$ for all $x,y \in R$.  It is well-known that any element $a \in R$ defines an inner derivation $[a,-] \colon R \to R$, given by $x \mapsto [a,x] = ax - xa$.  
Here's the part that I'm worried may be considered "cheating":  It's rather easy to compute that the kernel of a derivation $d \colon R \to R$ is a subring of $R$, which contains the multiplicative identity if $R$ has one (using $d(1) = d(1 \cdot 1)=\cdots$). 
Now given a monoid $M$ and element $a \in M$, consider the monoid ring $R = \mathbb{Z}[M]$ as you mentioned above.  Let $d = [a,-] \colon R \to R$ be the inner derivation defined by the element $a$. Then $\ker(d)$ is a unital subring of $R$, in particular a submonoid of $R$. One readily sees that the centralizer of $a$ in $M$ is equal to $M \cap \ker(d)$, and is therefore a submonoid of $M$.
Like I said above, I'm not convinced that this answer is in the spirit intended by the question.  But I thought I would offer at least a proof from a rather different perspective.
A: I completely agree with the comment by Hagen von Eitzen. Therefore, I won't interpret the question as giving the most simple proof, but rather as how to generalize it. In fact, there are various variants. For now, I only flesh out the part about universal algebra; perhaps I will add something about monoidal categories later. I hope that this sheds some light on the "nature" of this basic observation. But in any case it doesn't seem to be completely formal: None of the usual categorical constructions produce this submonoid.
$~~~\textbf{1. Universal algebra}$
Given an algebraic theory $\tau$, a class $B$ of binary operations in $\tau$ and an optional constant $e$, assume the following:
a) For all $*,\circ \in B$, we have an equality of derived ternary operations $a * (b \circ c) = (a*b) \circ c = (a \circ b) * c = a \circ (b * c)$.
b) For all $* \in B$ we have $a*e=e*a$ as derived unary operations.
c) All $* \in B$ are "bihomomorphisms" with respect to all operations outside of $B$. That is, for every $n \in \mathbb{N}$ and every $n$-ary operation $e \neq \omega \in B^c$ we have $a * w(b_1,\dotsc,b_n) = w(a*b_1,\dotsc,a*b_n)$ as well as $w(b_1,\dotsc,b_n)*a = w(b_1*a,\dotsc,b_n*a)$ as derived $n+1$-ary operations.
When we don't use $e$, then b) is dropped, as well as the condition $e \neq \omega$ in c).

Observation. Let $M$ be a $\tau$-module and $a \in M$. Then $N=\{(x,y) \in M^2 : \forall * \in B : a*x=y*a\}$ is a submodule of $M^2$.
In particular, $\{x \in M : \forall * \in B : a*x=x*a\}$ is a submodule of $M$.

Proof. Clearly $(e,e) \in N$. Let $(x,y),(x',y') \in N$, then for all $\circ \in B$ we have $(x \circ x',y \circ y') \in M$, since for all $* \in B$ we have
$a*(x \circ x') = (a*x) \circ x' = (y*a) \circ x' = y*(a \circ x')=y*(y' \circ a) = (y \circ y') * a$.
This shows the closure property with respect to $B$. If $\omega \in B^c$ is $n$-ary and $(x_i,y_i) \in N$ for $1 \leq i \leq n$, then $(\omega(x_1,\dotsc,x_n),\omega(y_1,\dotsc,y_n)) \in N$, since for all $* \in B$ we have
$a*\omega(x_1,\dotsc,x_n) = \omega(a*x_1,\dotsc,a*x_n)=\omega(y_1*a,\dotsc,y_n*a)=\omega(y_1,\dotsc,y_n)*a$. $~~\square$
General remark. When in b) we even demand $a*e=a=e*a$, then by a) $B$ consists of at most one binary operation.
Example 1. Let $\tau$ be the theory of semigroups with $B$ consist of the product. Then the conditions are satisfied, so that for every semigroup $H$ and $a \in H$ we have that $\{(x,y) \in H^2: a*x=y*a\}$ is a subsemigroup of $H^2$.
Example 2.  Let $\tau$ be the theory of monoids with $B$ consist of the product and $e$ the unit element. Then the conditions are satisfied. Thus, for every monoid $M$ and $a \in M$ we have that $\{(x,y) \in M^2 : a*x=y*a\}$ is a submonoid of $M^2$.
Example 3. Let $\tau$ be the theory of rings (optionally unital and/or commutative) with $B,e$ as before. Then the conditions are satisfied. Hence, if $R$ is a ring and $a \in R$, then $\{(x,y) \in R^2 : a*x=y*a\}$ is a subring of $R^2$. The same works with semirings.
Non-Example 4. Let $\tau$ be the theory of $\star$-rings, i.e. rings equipped with an involutive antiautomorphism. Then c) is not satisfied. And in fact, if $R$ is a $\star$-ring and $a \in R$, then $\{x \in R : ax=xa\}$ is not always a sub-$\star$-ring of $R$. A necessary condition is that $a$ is normal, i.e. that $a$ commutes with $a^\star$. A sufficient condition is that $a$ is self-adjoint, i.e. that $a=a^\star$.
Observe, however, that $\{x \in R : ax=xa, a^\star x = x a^\star\}$ is a sub-$\star$-ring of $R$. More generally, if $S \subseteq R$ is a sub-$\star$-ring of $R$, then its centralizer $\{x \in R : \forall a \in S : ax=xa\}$ is a sub-$\star$-ring of $R$. This fact is quite important in the theory of von Neumann algebras, a branch of modern functional analysis. However, the corresponding statement for theories $\tau$ does not hold without further assumptions on $\tau$!
I hope that this illustrates that the observation is not completely formal. Instead, it is a quite interesting one, which deserves more attention in other categories as well.
$~~~\textbf{2. Monoidal categories}$
The observation for monoids generalizes as follows: If $M$ is a monoid and $N$ is a submonoid of $M$, then its centralizer $C(N) = \{x \in M : \forall n \in N : xn=nx\}$ is a submonoid of $M$. Now, this statement internalizes into an arbitrary closed symmetric monoidal category $\mathcal{C}$ with equalizers:
Let $(M,\mu,e)$ be a monoid object in $\mathcal{C}$, and let $(N,\mu,e)$ be a submonoid of $M$, or even more generally any monoid equipped with a homomorphism $i : N \to M$ of monoid objects. There are two morphisms $\check{f},\check{g}: M \otimes N \rightrightarrows M$, namely the composition $M \otimes N \xrightarrow{M \otimes i} M \otimes M \xrightarrow{\mu} M$, as well as the composition $M \otimes N \xrightarrow{M \otimes i} M \otimes M \xrightarrow{S} M \otimes M \xrightarrow{\mu} M$, where $S$ denotes the symmetry. These correspond to two morphisms $f,g : M \rightrightarrows \underline{\hom}(N,M)$. Let $j : C(S) \hookrightarrow M$ be their equalizer. Then one can prove that $C(S)$ carries a unique monoid structure in such a way that $j$ becomes a homomorphism of monoids. Remark that this cannot be purely formal, for example since $f,g$ are not homomorphisms of monoids. I will omit the proof, because it is just a straight forward generalization of the case $\mathcal{C}=\mathsf{Set}$. One just as to "diagram-ize" the element calculations.
There are lots of closed symmetric monoidal categories, where this can be applied. For $\mathsf{Ab}$, we get centralizers for subrings. For $\mathsf{Mod}(R)$ we get centralizers for sub-$R$-algebras. For $\mathsf{Sh}(X)$ we get centralizers for sub(sheaves of rings on $X$). I am also pretty sure that the statement holds for higher categories, so that for example we get centralizers for subring spectra.
A: A few years later, I've found the following:
Convert $M$ to a single-object category. Then, the center $\{x: \forall a. ax = xa\}$ is the set of endomorphisms of the identity functor $1_M$, i.e. the set of natural transformations $1_M \Rightarrow 1_M$.
To obtain $\{x: ax = xa\}$ for a fixed $a$, we note that it's equal to $\{x: \forall n. a^n x = x a^n \}$. Instead of the identity functor $M \to M$, we look at the injection $\iota : \{a^n\} \to M$ and consider endomorphisms $\iota \Rightarrow \iota$.
