Ultraproducts and Elementary Embeddings Let $K= \{A_i: i\in \omega\}$ be a countable collection of $L-$structures. 
Suppose that for each $A_i, A_j$ in $K$, $\exists A_p \in K$ such that $i,j< p$ and $A_i \prec A_p $ and $A_j \prec A_p$. 
Suppose $D$ is a non-principal ultrafilter over $\omega$. Then, does it follow that for each $A_i \in K$, $A_i \prec \prod_D K$ (If not, could any strengthening of our hypothesis make it true)?
Notice that for every cofinite set $H$ of $\omega$, we have the following:
For any $A_i$ and $A_j$ ($i \in \omega$, $j \in H$), there exists a $p \in H$ such that $A_i, A_j \prec A_p$. 
 A: This could fail for very simple reasons if you don't control the cardinality of your structures. Suppose without loss of generality that the set of even numbers is in your ultrafilter.
Let the structures in question be just pure sets, and for all $n$, $A_{2n}$ is countably infinite, while $A_{2n+1}$ has cardinality greater than continuum. This sequence satisfies your assumptions, but the ultraproduct has cardinality at most continuum (it's a quotient of the product of all $A_{2n}$), so it can't contain a copy of any $A_{2n+1}$.
More generally, your assumption is essenetially equivalent to saying that all $A_n$ are elementarily equivalent: if this is the case, you can just pick an infinite set which is not in $D$ and put there structures into which all preceding $A_i$'s all embed, without changing the other $A_i$ -- this will not change the ultraproduct, as you only modify a $D$-small set, but will yield your assumption.
This is enough if all $A_i$ are countable: the ultraproduct will be $\omega$-saturated, which allows a recursive construction of an embedding (by extending finite partial elementary functions), but for general structures it's doubtful, even if you do somehow control the cardinality.
What you want will hold if you assume that the set $p$ of witnesses is large, so for any $i$ and for almost all $p$ (it can be just $D$-almost-all, though of course cofinitely many is good enough) we have $A_i\preceq A_p$, and obviously you don't need $j$ for this one, and the proof should be straightforward.
A: I'd like to expand on tomasz's last paragraph, just to emphasize that you can get what you want without any further assumptions on the collection of structures, just by picking your ultrafilter more carefully.
For each $i\in \omega$, let $C_i = \{j\in \omega\mid A_i \prec A_j\}$. Let's call this the cone above $A_i$. Now let $\text{Cone} = \{X\subseteq \omega\mid \exists i\,C_i\subseteq X\}$. This is called the cone filter - it's the filter generated by the cones. To check that it's a proper filter, you just need to check that the set of cones has the finite intersection property, which is an easy consequence of your assumption that the set of structures has the joint embedding property.
Now let $A = \prod_{i\in\omega} A_i/U$, the using any ultrafilter $U\supseteq \text{Cone}$. For all $i$, we have a natural elementary embedding $A_i\prec A$, mapping an element $a\in A_i$ to the class $[a_i]_{i\in \omega}$, where $a_j$ is the image of $a$ in $A_j$ when $j\in C_i$ and arbitrary otherwise. This is well-defined, since $C_i\in U$.
