Consider square matrices over a field $K$. I don't think additional assumptions about $K$ like algebraically closed or characteristic $0$ are pertinent, but feel free to make them for comfort. For any such matrix $A$, the set $K[A]$ of polynomials in $A$ is a commutative subalgebra of $M_n(K)$; the question is whether for any pair of commuting matrices $X,Y$ at least one such commutative subalgebra can be found that contains both $X$ and $Y$.
I was asking myself this in connection with frequently recurring requests to completely characterise commuting pairs of matrices, like this one. While providing a useful characterisation seems impossible, a positive anwer to the current question would at least provide some answer.
Note that in many rather likely situations one can in fact take $A$ to be one of the matrices $X,Y$, for instance when one of the matrices has distinct eigenvalues, or more generally if its minimal polynomial has degree $n$ (so coincides with the characteristic polynomial). However this is not always possible, as can be easily seen for instance for diagonal matrices $X=\operatorname{diag}(0,0,1)$ and $Y=\operatorname{diag}(0,1,1)$. However in that case both will be polynomials in $A=\operatorname{diag}(x,y,z)$ for any distinct values $x,y,z$ (then $K[A]$ consists of all diagonal matrices); although in the example in this answer the matrices are not both diagonalisable, an appropriate $A$ can be found there as well.
I thought for some time that any maximal commutative subalgebra of $M_n(K)$ was of the form $K[A]$ (which would imply a positive answer) for some $A$ with minimal polynomial of degree$~n$, and that a positive answer to my question was in fact instrumental in proving this. However I was wrong on both counts: there exist (for $n\geq 4$) commutative subalgebras of dimension${}>n$ (whereas $\dim_KK[A]\leq n$ for all $A\in M_n(K)$) as shown in this MathOverflow answer, and I was forced to correct an anwer I gave here in the light of this; however it seems (at least in the cases I looked at) that many (all?) pairs of matrices $X,Y$ in such a subalgebra still admit a matrix $A$ (which in general is not in the subalgebra) such that $X,Y\in K[A]$. This indicates that a positive answer to my question would not contradict the existence of such large commutative subalgebras: it would just mean that to obtain a maximal dimensional subalgebra containing $X,Y$ one should in general avoid throwing in an $A$ with $X,Y\in K[A]$. I do think these large subalgebras easily show that my question but for three commuting matrices has a negative answer.
Finally I note that this other answer to the cited MO question mentions a result by Gerstenhaber that the dimension of the subalgebra generated two commuting matrices in $M_n(K)$ cannot exceed$~n$. This unfortunately does not settle my question (if $X,Y$ would generate a subalgebra of dimension${}>n$, it would have proved a negative answer); it just might be that the mentioned result is true because of the existence of $A$ (I don't have access to a proof right now, but given the formulation it seems unlikely that it was done this way).
OK, I've tried to build up the suspense. Honesty demands that I say that I do know the answer to my question, since a colleague of mine provided a convincing one. I will however not give this answer right away, but post it once there has been some time for gathering answers here; who knows somebody will prove a different answer than the one I have (heaven forbid), or at least give the same answer with a different justification.