I have learnt here that, given a group $G$ and $H \unlhd G$, it is $gC_G(h) \cap H \ne \emptyset,\forall h \in H,g \in G$, if and only if $G$ fixes the conjugacy classes of $H$ under conjugation. Then, it seems that the following holds:
Corollary. $K$ a group; put $G:=\operatorname{Aut}(K)$ and $H:=\operatorname{Inn}(K)$; $G$ fixes the conjugacy classes of $H$ under conjugation, and then the above claim holds.
Proof. $\operatorname{Inn}(K)=im_\varphi$, where $\varphi \colon K \rightarrow \operatorname{Aut}(K)$ is defined by $a \mapsto \varphi_a$, being $\varphi_a(g):=a^{-1}ga, \forall g \in K$. Now, $\forall \sigma \in \operatorname{Aut}(K)$, $\sigma^{-1}\varphi_a\sigma=\varphi_{\sigma^{-1}(a)}$; but also, $\forall \sigma \in \operatorname{Aut}(K)$, $\exists b \in K \mid \sigma^{-1}(a)=\varphi_b^{-1}(a)$. Therefore, $\forall \sigma \in \operatorname{Aut}(K)$, $\sigma^{-1}\varphi_a\sigma=\varphi_{\sigma^{-1}(a)}=\varphi_{\varphi_b^{-1}(a)}=\varphi_b^{-1}\varphi_a\varphi_b$, for some $b \in K$. $\blacksquare$
Does this corollary really hold? Is the proof correct?
I just remembered GroupProps gives conjugacy class structure for some small groups, so I will post as an answer.
$S_n$ does not always fix the conjugacy classes of $A_n$. For example if $n=5$ as in the link $(1,2,3,4,5)$ and $(1,2,3,5,4)$ are in two conjugacy classes of $A_5$ but in the same class of $S_5$. Hence $K=A_5$ is a counterexample.
The mistake in the proof is the existence of $b$ with $\sigma^{-1}(a)=\varphi_b^{-1}(a)$ - this seems to be assuming the result that you are trying to prove.