1. Clement said the Phoenix had its origin in "Eastern lands, that is, in Arabia", far away from Egypt. This indicates that the Sinai Peninsula was not viewed by Clement as Arabia.
2. Notice that Clement, understanding the myth of the Phoenix correctly says that just before it dies, it flew from Arabia to the city of Heliopolis in Egypt where it was reborn in flames.
3. Here are three ancient texts from Clement, Lactantius, Herodotus that show that the they viewed Arabia as the place where spices came from.

A. The Myth of the Phoenix: Clement, Lactantius, Herodotus

1. "Let us consider that wonderful sign [of the resurrection] which takes place in Eastern lands, that is, in Arabia and the countries round about. There is a certain bird which is called a phoenix. This is the only one of its kind, and lives five hundred years. And when the time of its dissolution draws near that it must die, it builds itself a nest of frankincense, and myrrh, and other spices, into which, when the time is fulfilled, it enters and dies. But as the flesh decays a certain kind of worm is produced, which, being nourished by the juices of the dead bird, brings forth feathers. Then, when it has acquired strength, it takes up that nest in which are the bones of its parent, and bearing these it passes from the land of Arabia into Egypt, to the city called Heliopolis. (First Epistle of Clement to the Corinthians, Chapter 25, The Phoenix an Emblem of Our Resurrection.)
2. Lactantius, lived 140 years after Clement (320 AD) and confirms the definition of Arabia: "They call it a phoenix, and relate that every five hundred years it comes into Egypt, to that which is called the altar of the sun, and brings with it a great quantity of cinnamon, and cassia, and balsam-wood, and standing towards the east, as they say, and praying to the sun, of its own accord is burnt, and becomes dust; but that a worm arises again out of those ashes, and that when the same is warmed it is formed into a new-born phoenix; and when it is able to fly, it goes to Arabia, which is beyond the Egyptian countries." (Lactantius, The phoenix, 320 AD)
3. "They have also another sacred bird called the phoenix which I myself have never seen, except in pictures. Indeed it is a great rarity, even in Egypt, only coming there (according to the accounts of the people of Heliopolis) once in five hundred years, when the old phoenix dies. Its size and appearance, if it is like the pictures, are as follow:- The plumage is partly red, partly golden, while the general make and size are almost exactly that of the eagle. They tell a story of what this bird does, which does not seem to me to be credible: that he comes all the way from Arabia, and brings the parent bird, all plastered over with myrrh, to the temple of the Sun, and there buries the body. In order to bring him, they say, he first forms a ball of myrrh as big as he finds that he can carry; then he hollows out the ball, and puts his parent inside, after which he covers over the opening with fresh myrrh, and the ball is then of exactly the same weight as at first; so he brings it to Egypt, plastered over as I have said, and deposits it in the temple of the Sun. Such is the story they tell of the doings of this bird. (Herodotus 2.73)
4. "Phoenix, a fabulous bird connected with the worship of the sun, especially in ancient Egypt and in classical antiquity. The phoenix was said to be as large as an eagle, with brilliant scarlet and gold plumage and a melodious cry. Only one phoenix existed at any time, and it was very long-lived-no ancient authority gave it a life-span of less than 500 years. As its end approached, the phoenix fashioned a nest of aromatic boughs and spices, set it on fire, and was consumed in the flames. From the pyre miraculously sprang a new phoenix, which, after embalming its father's ashes in an egg of myrrh, flew with them to Heliopolis ("City of the Sun") in Egypt, where it deposited them on the altar in the temple of the Egyptian sun god, Re. A variant of the story made the dying phoenix fly to Heliopolis and immolate itself in the fire burning on the altar, a young phoenix rising from the flames. The bennu, a heron, was traditionally associated with sun worship in Egypt, appearing on monuments as a symbol of the rising sun and of the life after death. But despite the common religious associations, the phoenix as described in literature did not at all resemble a heron in appearance, and its home was not in Egypt but nearer the rising sun (normally in Arabia or India, where spices for the nest and egg were plentiful). Probably the phoenix story originated in the Orient and was assimilated to Egyptian sun worship by the priests of Heliopolis. The adaptation of the myth to an Egyptian environment helped to bring about the connection between the phoenix and the palm tree (also called phoenix in Greek), which was long associated with sun worship in Egypt." (Encyclopedia Britannica, Phoenix)