This may be an issue of semantics. Here is my impression:
Satan sinned prior to Adam and Eve sinning, as Richard indicated in his answer (which you linked). At that time he "fell" in the sense that DTest was asking about in his question. (i.e. "fell from grace".)
However, after Satan's initial sin, he appears to have still had access to the realm where the angels stand before God (which we call "heaven"). This is what I was getting at in my "examples" link in my answer (which you linked). Here are the verses from Job that I was referring to:
Now there was a day when the sons of God came to present themselves before the Lord, and Satan also came among them. -Job 1:6
Again there was a day when the sons of God came to present themselves before the Lord, and Satan also came among them to present himself before the Lord. -Job 2:1
- (See also: Zechariah 3:1) I also linked a passage from Luke in which Jesus says that He was watching Satan falling from heaven when "the seventy" were rebuking demons. If he is still "falling from heaven" in Jesus' day, it seems logical to think he still had access to heaven, and must not have yet been banished in any ultimate sense.
The seventy returned with joy, saying, “Lord, even the demons are subject to us in Your name.” And He said to them, “I was watching Satan fall from heaven like lightning." -Luke 10:17-18
- The passage from Revelation 12 seems to be describing a much more ultimate banishment in which he is forced out of heaven by Michael's armies, there is "no longer a place found for them in heaven", and he is "thrown down to the earth", resulting in "woe to the earth" because once Satan realizes what has happened, he has "great wrath, knowing that he has only a short time." The context of this passage, which I was explaining in my answer (which you linked) seems to be about the End Times, and the casting down seems to happen after the ascension, since the resulting proclamation includes a description of how the "brethren" overcame Satan by the blood of Jesus. It seems unnatural to interpret this as describing an event that happened back in Genesis 1-3.
Ezekiel 28:12-19, which may be one of the points of confusion, is a prophecy against Tyre (specifically addressed to the King of Tyre). However, it is also partially addressing Satan, who was presumably working through the King of Tyre... for instance, in verses 12-15 it says things like "you were in Eden" and "you were the anointed cherub". It is true that the passage also says "I have cast you as profane from the mountain of God" and "I cast you to the ground". However, we need to read the entire passage and understand it as intended. For instance, it also says things like "by the abundance of your trade you were internally filled with violence" and "you profaned your sanctuaries", referring to the city, not Satan. Furthermore, there are statements like "I have destroyed you... from the midst of the stones of fire" and "I have brought fire from the midst of you; it has consumed you, and I have turned you to ashes on the earth". I don't know of anyone who teaches that this happened to Satan - at least not yet (Revelation 20:10).
(Isaiah 14:3-21 is the same sort of story, but is about Babylon instead of Tyre.)
If there are other passages which seem to contradict this, make a note in the comments and I'll take a look. This is just my tentative understanding based on the passages I'm aware of. Hope that helps.