Yhyjyk

Many introductory Latin books will explain that Classical Latin has four diphthongs: ae and au are common, while oe and ei are rarer. (Eu and ui also show up, but if I understand right that's a Greek influence that doesn't appear in native words.)

However, it's hard for me to think of any common Latin words with an ei diphthong. For example, the pronoun eī is pronounced with two syllables, and ē-iciō "to throw out" with three.

Cassel's dictionary lists dē-inde as an example of the diphthong. But how can I, as a non-native speaker, keep track of which is which? Both dē-inde and ē-iciō have a long ē, a short i, and a morpheme boundary in the middle. Why does one have a diphthong and the other not? Is there a rule I can learn for this?

(P.S. Does anyone write the diphthong as ej and the hiatus as ei? That would be really convenient.)

(P.P.S. Oe mostly shows up in Greek words, but is also found in some nice native Latin roots, like foedus "treaty".)

The diphthong ei is found before vowels: eius, peior.
I am not aware of occurrences before a consonant.

This is quite similar to ui appearing in cuius and huius.
It also appears in cui.
If you are unconvinced that it should not be cuī instead, see for example the occurrences in the Aeneid, including the very first syllable of a number of verses.

In an answer to the "Oh no!" question luchonacho mentioned the interjection ei.
Judging by this line in Ovid's Amores, it is a single diphthong unlike the pronoun(s) ei:

Ei mihi, quod dominam nec vir nec femina servas

"Ei" is almost never a diphthong.

The exact list of examples depends on what you call a "diphthong". Cser (2016) argues that Latin has no genuine diphthongs, only vowel + glide sequences. Cser says that, if we set aside words with geminate /j.j/, /ej/ occurs in the following three related words: deinde, dein, deinceps (p. 32). As far as I know, these are never written with <ej>. L&S says that dehinc is frequently a monosyllable in poetry, which could be interpreted as implying a pronunciation /dejnk/.

Scansion alone wouldn't tell us the exact pronunciation of <ei> here, so I'm not sure why Cser thinks these words had /ej/ specifically, as opposed to something like /eː/, /iː/, or even /e/ or /i/ (with the syllable being heavy because of coda /n/).

Some sources seem to categorize the disyllabic pronunciation of deinde and/or dehinc as an example of synizesis, alongside e.g. the pronunciation of "eo" in one syllable in words like alveo.

/ej.j/ before a vowel

Some instances of <ei> are thought to have been pronounced /ej.ji/. Cser mentions reicere (p. 149) and the genitive form Pompei (p. 13).

Words with /ej.j/ followed by a vowel other than /i/ have had spelling variants with <ej>, like the word eius/ejus mentioned in Joonas's answer. One thing to keep in mind is that some sources, particularly older dictionaries like L&S, may write this as ēi, where the macron represents syllable weight rather than necessarily representing the length of the vowel itself. Intervocalically, /j/ is almost always found geminate in Latin—that is, as /j.j/, but it became usual to write this with just a single letter I (or in modern-era texts, J).

There are some prefixed words where, based on etymology, we would expect /eː.j/, although metrically there's no way of distinguishing this from /ej.j/. You mentioned eicio, which is thought to have started with /eː.ji/; another word that is thought to have had /eː.j/ is seiungo.

(For more discussion of pronunciations like /ji/, /j.ji/, or /j.j/ for <i> in contexts other than just <ei>, see my answer to When is an I not an I?).

other /ej/ before a consonant?

There might be a few other examples of /ej/ before a consonant, but it's not necessarily clear. Cser brings it up as a potential pronunciation of <ei> in "anteis", "anteit" and "anteire" but suggests that /iː/ is a more likely pronunciation in this word (p. 150).