The Harrowing of Hell
Theologically, it is true that all humans would be destined to end up in hell were it not for the saving grace that flows from Jesus' death on the Cross.
This is the point of the legends about how Jesus broke down the gates of Hell and set the prisoners free.
Jesus' saving action is not confined by time limits. Just as He gave grace to Our Lady in her Immaculate Conception and to John the Baptist in his mother's womb before He was crucified, so He gave saving grace to many children of Abraham (Moses, Elijah, the prophets, the People of God) before He was born.
Elijah going to heaven (hashamayim) suggests that a simplistic, time-based thinking about pre-resurrection salvation is wrong. Elijah does not go to Sheol. In the Transfiguration, Moses and Elijah appear in glory with Jesus. Prevenient grace give to Mary. Sign of God's power at work outside the bounds of space-time and our ordinary expectations about space-time.
Abraham and Lazarus are also pictured as being in Heaven. No mention of Baptism or faith in Jesus or anything. Of course, the medieval commentators see "the bosom of Abraham" as distinct from "Heaven" (sigh; "if it is a different word, it is a different reality," as with "and with your spirit"). Their faith in Jesus must be implicit rather than explicit. No one goes to Heaven except through Him. They are in Heaven. They are there because of faith in Him.
No mention of the apostles being baptized AFTER Jesus' death and resurrection. John's Last Supper account: "You are clean. You only need to wash your feet, not your whole body."
God's hands are not tied by time. He can out outside of time in a way that confounds our linear thinking.