I did some more research on this Michael Faust, and seem to have found even more strangeness.
Michael and Magdalena had several children, including a son, George Herman Faust. George married Minnie Kleis, the daughter of Henry and Christine Heine Kleis.
It appears that after Magdalena died (1885), Michael married Christine Heine Kleis, his son's mother-in-law. I found a death entry for Henry Kleis in 1882, and the 1885 Indianapolis City Directory lists Christina Kleis as the widow of Henry. Michael and Christine were married in Lebanon (Boone county) Indiana in 1886.
But this does nothing to help clear up the Amelia Cartheuser issue... so I am more confused than ever.