The picture is certainly more complex than you suppose. "Paradise," as translated in the LXX, primarily referred to the Garden of Eden, a place of fellowship with God and eternal life, from which man was banished. A question not addressed in the OT is what happened to it. This led to much speculation in Jewish and Christian thought about where it is and how it will be revealed in the future. The NT draws on this tradition. In 1 Enoch 17-33, Enoch is given a tour of Sheol where he sees both "the paradise of God" and "the accursed valley" of Gehenna in Sheol. The important thing to understand is that Sheol is not thought of as a place under the earth. It is rather a hidden nether region at the edge of the world, hidden by mountains and seas. In ch. 17-18, Enoch traverses mountains, a river of fire, and a great sea to reach a place "neither in heaven above nor in earth below" where the fallen angels were chained in prison (ch. 21). Then in ch. 22, after crossing a mountain, he found a region where the sinners and righteous were seperated awaiting judgment day. To the northwest over seven mountains lay the tree of life and New Jersalem (ch. 24-26). And next to it lay "the accursed valley" of Gehenna (ch. 27). All of this lies in the hidden realm of Sheol. In 1 Enoch 60:8, Paradise is mentioned as "where the elect and the righteous ones dwell" and where Enoch, who was "taken by God," still resides. This notion of Paradise, consistent with Near Eastern cosmology (where, in the Gilgamesh Epic, the immortal Utnapishtim resides at the edge of the world) and the description of Eden in Genesis as a place in the distant East, is certainly the older conception. It is also attested by Josephus, 2 Baruch 4:1-7, and in rabinnical literature.
A later variation of this belief is that the Garden of Eden, or Paradise, hidden at the edge of the world, is a gateway to heaven. This is the view of the Testament of Abraham 11. Here Michael the Archangel takes Abraham "toward the east, to the first gate of heaven" (11:1). Actually here, in the netherworld, there were TWO gates. In front of them stands "the first-formed Adam" who observes the souls of the dead being seperated and passing into either gate:
When he sees many souls entering through the straight gate, then he arises and sits on his throne rejoicing and exulting cheerfully, because this straight gate is the gate of the righteous, which leads to life, and those who enter through it come into Paradise. And on account of this the first-formed Adam rejoices, since he sees the souls being saved. And when he sees many souls entering through the broad gate, then he pulls the hair of his head and casts himself on the ground crying and wailing bitterly; for the broad gate is the gate of the sinners, which leads to destruction and eternal punishment. (Testament of Abraham 11:10-11)
Like 1 Enoch, the souls of the wicked and righteous are separated in Sheol in "the East" but Paradise is entered through a "gate of heaven," linking Paradise with heaven. 4 Ezra 4:7-9 also mentions "the entrances of Paradise" and equates Paradise with "heaven". In both cases, Paradise/heaven is directly accessible in Hades/Sheol via an "entrance" or "gate".
A still later development is locating Paradise in "third heaven". According to the Life of Adam and Eve 48, Adam dies and his soul washes up at the Acheron where Michael the Archangel takes him "back to Paradise, which is in third heaven" (v. 40), where "the flowers of Paradise, with their sweet fragrance" were still to be found (v. 2). Similarly, 2 Enoch 8:1-3 locates the "Paradise of Eden" in "third heaven":
And those men took me from there, and they brought me up to the third heaven and set me down there. Then I looked downward and I saw Paradise. And that place is inconceivably pleasant. And I saw the trees in full flower. And their fruits were ripe and pleasant-smelling, with every food in yield and giving off profusely a pleasant fragrance. And in the midst of them was the tree of life, at that place where the Lord takes a rest when he goes into paradise. (2 Enoch 8:1-3)
Paul also mentions Paradise in "third heaven" in 2 Corinthians 12:2. Paradise is still the dwelling-place of the righteous souls as the Life of Adam and Eve, Testament of Abraham, 2 Enoch and other sources claim. But there is some tension between the Jewish belief of the dead sleeping in Sheol/Hades awaiting Judgment Day and the belief of them already in heaven in Paradise. One cannot hammer out a single doctrine out of these conflicting beliefs. Jesus in Luke 23:42 certainly understands that Paradise is a place of bliss that exists NOW and a place where the righteous enter at death; he is promising the repentant sinner that he will be with him there on the very day of his death. This is in complete conformity with the concept in 1 Enoch and the Testament of Abraham that the righteous go immediately into Paradise at death. It also fits with the concept in Luke 16 where such separation also occurs at death and the righteous share fellowship with Abraham in a state of bliss.
The idea in Revelation 22 of Paradise (New Jerusalem with gardens and the Tree of Life) being descended from heaven at the creation of a new heavens and earth is related to these developments. Here Paradise has been hidden in heaven and has always existed since creation, but now it is finally REVEALED to mankind as creation is restored. This concept is very close to 2 Baruch 4 where the Paradise that God created for Adam was taken away and preserved in heaven where it is prepared into New Jerusalem which will be revealed at the coming of the Messiah. And in a prophecy on the coming of the Messiah in the Testament of Levi 18:10-11, the Messiah is said to "open the gates of paradise; he shall remove the sword that has threatened since Adam, and he will grant to the saints to eat of the Tree of Life. The spirit of holiness shall be upon them, and Beliar shall be bound by him." In Sibylline Oracle Fr. 3:46-49, we also read: "Those who honor the true eternal God inherit life, dwelling in the luxuriant garden of Paradise for the time of eternity, feasting on the sweet bread from starry heaven." One of the disciples of John the Presbyter (who is the likely author of Revelation), Papias, also shared a similar view and believed in a literal descent of Paradise from heaven onto the earth and who described the material blessings of this "Paradise on Earth" in language almost verbatim from 2 Baruch. We can thus see how the different concepts of Paradise in the NT and early Christian writings fit into the contemporary Jewish speculation of the day.
Leolaia