Let $A$ be a nonderogatory matrix. This means the characteristic polynomial and the minimal polynomial of $A$ are coincide. Or, equivalently, every matrix $X$ that satisfies $XA=AX$ can be written as a polynomial of $A$. If $AX=XA$ and $XA=A^TX$, prove that $X$ is a symmetric (complex) matrix.
So since $X=f(A)$ for some complex polynomial $f(x)$, from $XA=A^TX$ we can deduce $X^2=X^TX$, but only when $X$ is a real matrix, we can have $X$ is symmetric. I wonder if the original question is wrong, that we should add $X$ being a real matrix? I also check some low order nonderogatory matrices but fail to find a counterexample. Can anyone help me? Thanks!
The hypothesis is that $A=SDS^{-1}$ with $D$ diagonal and all its diagonal entries distinct. From $AX=XA$, it follows that $X=SES^{-1}$ with $E$ diagonal.
The equality $XA=A^TX$ can be written as $$ SEDS^{-1}=S^{-T}DS^TSES^{-1}. $$ Multiplying on the left by $S^T$ and on the right by $S$, we get $$ S^TSED=DS^TSE. $$ For any $k$ such that $E_{kk}\ne0$, the entries in the above equality give us $$ (S^TS)_{kj} D_{jj}=(S^T)_{kj}D_{kk}. $$ So, $E_{kk}\ne0$ and $k\ne j$ imply $(S^TS)_{kj}=0$.
Now, if $E_{kk}\ne0$ or $E_{jj}\ne0$, $$ (ES^TS)_{kj}=E_{kk}(S^TS)_{kj}=\delta_{kj}E_{kk}(S^TS)_{kk} $$ $$ (S^TSE)_{kj}=(S^T)_{kj}E_{jj}=\delta_{kj}(S^TS)_{kk}E_{jj} $$ and then $(ES^TS)_{kj}=(S^TSE)_{kj}$. If $E_{kk}=E_{jj}=0$, we also get $(ES^TS)_{kj}=(S^TSE)_{kj}$. So $$ ES^TS=S^TSE. $$ Multiply by $S^{-1}$ on the right, and by $S^{-T}$ on the left, to get $$ X^T=S^{-T}ES^T=SES^{-1}=X. $$