This came up in the comments to an answer of Joel's. Suppose $\mathcal{M}_i$ ($i\in I$) are elementarily equivalent structures in the same fixed signature and $\mathcal{U}$ is an ultrafilter on $I$. Must some $\mathcal{M}_i$ elementarily embed into $\prod_{i\in I}\mathcal{M}_i/\mathcal{U}$?
I'm happy to add further restrictions to make this question easier, such as setting $I=\omega$ or requiring the language of the structures to be finite.
Here is another example, which is inspired by James's answer, but I find this one a little simpler.
Let $T$ be the theory of an equivalence relation $\sim$ with infinitely many classes, all infinite, plus countably many constants $c_0,c_1,c_2,\ldots$, taken from different equivalence classes. This is a complete theory, which can be seen by elimination of quantifiers.
Let $M_n$ be a model with all equivalence classes countable, except the equivalence class of $c_n$, which we take of size $\mathfrak{c}^+$. Let $M=\prod_n M_n/\mu$ be the ultraproduct of the $M_n$ by a nonprincipal ultrafilter $\mu$ on $\omega$.
The size of the equivalence class of $c_n$ in $M$ is determined by functions from $\omega$ to the corresponding $[c_n]^{M_i}$, which are all countable except for $M_n$. Since no one factor is relevant for the nature of $M$, it follows that $[c_n]^M$ has size continuum. Thus, $M_n$ does not embed in $M$.
So none of the factors embed into the ultrapower, as desired.
Optimal size. For the reasons mentioned in Emil's comment below, if CH holds this size $\mathfrak{c}^+$ is the best possible. I am unsure whether there could be a smaller counterexample if CH fails.
Analyzing the ultrapower further. I find it interesting to notice a few things about the ultrapower structure — in fact we can describe it exactly. It will have a bunch of other equivalence classes not containing any of the constants $c_n$. Any function $f$ with $f(n)$ not almost always chosen from the class of the same constant $c_k$ will represent a new equivalence class in the ultrapower. These will all have size continuum also (and there are continuum many of them), except for the one equivalence class arising from functions $f$ with almost always $f(n)\in[c_n]^{M_n}$, choosing from the big class at these coordinates. This one equivalence class in the ultrapower will have size $(\mathfrak{c}^+)^\omega=\mathfrak{c}^+$.
So the ultraproduct $M$ consists of continuum many equivalence classes of size continuum, with countably many of them occupied by constants $c_n$, plus one more equivalence class of size $\mathfrak{c}^+$.
Generalizing to arbitrary ultrafilters. The construction generalizes to any uniform ultrafilter $\mu$ on any set $I$. We have an equivalence relation with infinitely many classes, all infinite, plus constants $c_i$ for each $i\in I$, and inequivalent. Let $M_i$ be a model with all equivalence classes countable, except for $[c_i]^{M_i}$, which should have size larger than $\omega^I$. The ultrapower $M=\prod_i M_i/\mu$ will have $[c_i]^M$ of size at most $\omega^I$, and so no $M_i$ will embed into $M$.
I realized there's an easier example that doesn't need a measurable cardinal.
Consider the language $\def\Lc{\mathcal{L}}\Lc$ which consists of unary predicates $U_n$ for each $n<\omega$. Consider the $\Lc$-structure whose underlying set is $2^\omega$ with each $U_n$ interpreted in such a way that $U_n(\alpha)$ holds if and only if $\alpha(n) = 1$. Let $T$ be the theory of this structure. For any $\Lc$-structure $M$ and any $a \in M$, let $U(a)$ be the unique element of $2^\omega$ satisfying that for each $n<\omega$, $U_n(a)$ holds if and only if $\alpha(n) = 1$. Note that an $\Lc$-structure $M$ is a model of $T$ if and only if the set $\{U(a) : a \in M\}$ is dense in $2^\omega$.
Let $\kappa = (2^{\aleph_0})^+$. Let $N$ be a fixed countable model of $T$. For each $i<\omega$, let $M_i$ be the $\Lc$-structure whose universe consists of $N$ and $\kappa$, where for any $a \in N$ the value of $U(a)$ in $M_i$ is the same as the value of $U(a)$ in $N$ and for any $b \in \kappa$, the value of $U(b)$ is $1^i000\dots$ (i.e., $i$ instances of $1$ followed by $0$'s). Fix any non-principal ultrafilter $\def\Uc{\mathcal{U}}\Uc$ on $\omega$ and let $M$ be the ultraproduct of the family $(M_i)_{i<\omega}$ with respect to $\Uc$. A quick counting argument shows that for any $\alpha \in 2^\omega$ other than the all $1$'s sequence, there are only continuum-many $a \in M$ such that $U(a) = \alpha$, which is enough to imply that for each $i<\omega$, $M_i$ does not have an elementary embedding into $M$.
We can get more examples from measurable cardinals and measurable limits of measurable cardinals.
For every set of ultrafilters $M$, there is a structure $\mathcal{A}$ such that if $\mathcal{U},\mathcal{V}\in M$, then there is an elementary embedding from $\mathcal{A}^\mathcal{U}$ to $\mathcal{A}^\mathcal{V}$ if and only if $\mathcal{U}\leq_{RK}\mathcal{V}$ in the Rudin-Kiesler ordering (for example, $\mathcal{A}$ could a structure with cardinality greater than the underlying set of each ultrafilter on $M$ and where every operation is a fundamental operation and every relation is a fundamental relation). I believe that this correspondence between elementary embeddings and the Rudin-Kiesler ordering can be found in Andreas Blass' dissertation. I think you can also let $\mathcal{A}=V_\alpha$ for large enough $\alpha$.
Suppose that $I$ is a set. Suppose that $\mathcal{U}$ is a non-principal ultrafilter on $I$, and $\mathcal{U}_i$ is an ultrafilter on some set $X_i$ for $i\in I$. For simplicity, suppose that $X_i\cap X_j=\emptyset$ for $i\neq j$. Let $\mathcal{V}$ be the ultrafilter on $\bigcup_{i\in I}X_i$ where $R\in\mathcal{V}$ precisely when $\{i\in I\mid R\cap X_i\in\mathcal{U}_i\}\in\mathcal{U}$. We observe that $\prod_{i\in I}\mathcal{A}^{\mathcal{U}_i}/\mathcal{U}\simeq\mathcal{A}^{\mathcal{V}}$ for all structures $\mathcal{A}$. We shall now produce examples where $\mathcal{U}_i\not\leq_{RK}\mathcal{V}$ for $i\in I$.
(1) Suppose that $\mu$ is a measurable limit of measurable cardinals. Let $I$ be a set of measurable cardinals below $\mu$ with $|I|=\mu$. Suppose that the ultrafilter $\mathcal{U}$ is $\mu$-complete and $\mathcal{U}_\alpha$ is $\alpha$-complete but not $\mu$-complete whenever $\alpha\in I$. Then the ultrafilter $\mathcal{V}$ is $\mu$-complete. However, if $\mathcal{W}\leq_{RK}\mathcal{V}$, then $\mathcal{W}$ must also be $\mu$-complete, so $\mathcal{U}_\alpha\not\leq_{RK}\mathcal{V}$ for $\alpha\in I$.
(2). I claim that if $\mu$ is a measurable cardinal, $|I|<\mu$, and each $\mathcal{U}_i$ is $\mu$-complete, and $\mathcal{W}$ is $\mu$-complete, then whenever $\mathcal{W}\leq_{RK}\mathcal{V}$, there is some $Q^\sharp\in \mathcal{U}$ where $\mathcal{W}\leq_{RK}\mathcal{U}_i$ for $i\in Q^\sharp$. Suppose that $\mathcal{W}$ is supported on a set $X$ and $f:\bigcup_{i\in I}X_i\rightarrow X$ is a function such that if $R\subseteq X$, then $R\in\mathcal{W}$ if and only if $f^{-1}[R]\in\mathcal{V}$. If $R\subseteq X$, then let $R^\sharp=\{i\in I:f^{-1}[R]\cap X_i\in\mathcal{U}_i\}$. Observe that if $R\in\mathcal{W}$, then $R^\sharp\in\mathcal{U}$ and the mapping $R\mapsto R^\sharp$ is a Boolean algebra homomorphism from $P(X)$ to $P(I)$. Let $\mathbf{T}=\{R^\sharp:R\in\mathcal{W}\}$. For each $S\in\mathbf{T}$, there is some $S_\sharp\in\mathcal{W}$ with $(S_\sharp)^\sharp=S$. Therefore, by $\mu$-completeness and since $2^{|I|}<\mu$, we know that $\bigcap_{S\in\mathbf{T}}S_\sharp\in\mathcal{W}$. Therefore, if we set $Q=\bigcap_{S\in\mathbf{T}}S_\sharp$, then $Q^\sharp$ is the smallest element in $\mathbf{T}$. Now let $\mathcal{W}_1=\mathcal{W}\cap P(Q)$. Then $R^\sharp=Q^\sharp$ for $R\in\mathcal{W}_1$ and $R^\sharp=\emptyset$ for $R\in P(Q)\setminus\mathcal{W}_1$. If $i\in Q^\sharp$, then $f^{-1}[R]\cap X_i\in\mathcal{U}_i$ for $R\in\mathcal{W}_1$. Therefore, $\mathcal{W}\leq_{RK}\mathcal{U}_i$ for $i\in I$.
In particular, if $\mathcal{U}_j\leq_{RK}\mathcal{V}$, then there is some $Q^\sharp\in\mathcal{U}$ where $\mathcal{U}_j\leq_{RK}\mathcal{U}_i$ for $i\in Q^\sharp$. But there are a few ways to ensure that we cannot have $\mathcal{U}_j\leq_{RK}\mathcal{V}$ including the following:
i. Suppose that $\mu_i$ is a measurable cardinal with $\mu_i>|I|$ for $i\in I$, and $\mathcal{U}_i$ is a normal ultrafilter on $\mu_i$ for $i\in I$. Suppose furthermore that $\mathcal{U}_i\neq\mathcal{U}_j$ for $i\neq j$. Then since normal ultrafilters are Rudin-Keisler minimal, if $\mathcal{U}_j\leq_{RK}\mathcal{U}_i$, then either $\mathcal{U}_j$ is principal or $\mathcal{U}_j=_{RK}\mathcal{U}_i$ which contradicts our hypotheses.
ii. Suppose that $I$ is a well-ordered set and $\mu_i$ is a measurable cardinal with $\mu_i>|I|$ for $i\in I$ and that $\mu_i<\mu_j$ whenever $i<j$. Suppose furthermore that if $i<j$, then $\mathcal{U}_i$ is $\mu_i$-complete but where $|X_i|<\mu_j$. Then whenever $\mathcal{V}\leq_{RK}\mathcal{U}_i$ and $i<j$, the ultrafilter $\mathcal{V}$ is $\mu_i$-complete, but not $\mu_j$-complete, so if $\mathcal{U}_j\leq_{RK}\mathcal{U}_i$, then $i=j$.
