Netyjnd

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".

deinde and friends

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.

An Anthology of Informal Latin, 200 BC–AD 900: Fifty Texts with Translations and Linguistic Commentary, edited by J. N. Adams (2016), gives dende as a 2nd-century spelling of deinde (Chapter 22, "Letter of Claudius Terentianus (P. MICH. VIII.471, CEL 146), of the Early Second Century"; the text is sourced from Kramer (2007).

In the notes, Adams says that "the phonetics [of "synezesis" in deinde] tend not to be addressed", and that "it remains unclear in what way (or ways) the term was pronounced in the early period; for the scansion dĕīnde in Terence see Questa (2007: 439)."

Adams suggests that a form with ē developed eventually in Latin, bringing up cōgo from co- + ago as an example of a contraction resulting in a long vowel with quality of the first component. As evidence against reading the first syllable of <dende> as [dɛn], Adams brings up (obsolete) reflexes in Spanish and Portuguese with forms like dende: these point towards Proto-Western-Romance *e rather than *ɛ, because *ɛ would lead to the form *diende, which is apparently not attested ("information from Adam Ledgeway"). Adams says the same would go for Spanish dentro (not *dientro) from Latin de- + intro.

Adams doesn't seem to mention that Proto-Western-Romance *e corresponds not only to Latin ē, but also to Latin ĭ, which I think is relevant because de + ĭ > dĭ seems like a plausible alternative kind of contraction.

/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).