Do people in the Narakas (or non-human realms) remember their past lives? I'm asking about what ancient traditionalist wrote or believed, particularly the ones the reified the narkas, i.e. took them literally.

Us humans don't normally remember our past lives and this is made explicit in Mahayana, where one of the qualities of a Buddha is that they can remember past lives.

If people are reborn in hells and they don't know why they are there, I'm not sure how effective the punishment is. Did anyone come up with a rationalization for punishment for crimes they don't remember, or did people in the hells remember what they did?
Yes, they do know the kamma that lead them there. In fact, the governer in hell (king Yama) is regarded as a nice person who tries to help them recall any of their past good deeds before throwing them away to torture. If they happen to recall any good action, they'll be turned away to be born again in a higher realm. Such an instance is given in Devaduta sutta where king Yama tries to remind a new entrant of the five deva messengers that instigate people to do good in the human world. 

There's a nice background story to a Dhammapada verse where king Pasenadi consulted Buddha on hearing some weird sounds at night and this turning out to be four of his former friends now in Lohakumbhi hell trying to convey him a message on consequences of their sexual misconducts.


  Meanwhile, King Pasenadi, obsessed with sexual desire, could not
  sleep, and kept thinking out how he would get rid of the husband in
  the morning and take his wife. At about midnight, he heard some eerie
  sounds; actually, these were the doleful voices of four persons
  suffering in Lohakumbhi Niraya . Hearing those weird voices, the king
  was terrified. Early in the morning, he went to the Buddha, as advised
  by Queen Mallika. When the Buddha was told about the four voices the
  king heard in the night, he explained to the king that those were the
  voices of four beings, who were the sons of rich men during the time
  of Kassapa Buddha, and that now they were suffering in Lohakumbhi
  Niraya because they had committed sexual misconduct with other
  people's wives. Then, the king came to realize the depravity of the
  deed and the severity of the punishment. So, he decided then and there
  that he would no longer covet another man's wife.
  http://what-buddha-said.net/Canon/Sutta/KN/Dhammapada.Verse_60.story.htm


As for other realms, hungry ghosts and devas are also said to recall the kamma  that brought them there. Petavatthu and Vimanavatthu provide a number of stories of monks who encountered such beings and heard their stories.