The Shut Min Hashamayim was written by a Rishon in the time of Tosfos. He used to ask questions from Shamayim (Heaven) in a Sheilas Chalom (Dream Question) and write the answers down. Many of those questions are practical Halachic questions (for example, is the correct Tfillin Rashi or Rabbeinu Tam, etc).
This question is the subject of a teshuva of Rav Ovadia Yosef in Yabia Omer 1:41-42, and he returns to this subject in many later teshuvos as well. He writes regarding this question that דבר זה הוא מקצוע גדול בתורה (so imagine this question upvoted by R. Ovadia Yosef).
First of all, it isn't so clear that we actually do 'pasken' like the Shut min Hashamayim, though the Chida seemed to have insisted upon it. Second, isn't a bas kol or prophecy - it's a dream. Rav Ovadia writes
יש חילוק גדול בין מתנבא בשם ה' דרך נבואה, דבהא הוא דאמרינן שאין נביא רשאי לחדש דבר מעתה, לחולם חלום, שאינו אלא אחד מששים בנבואה (ברכות נז:), ומש"ה אין איסור זה נוהג בחלום, שאינו תוקע עצמו לדבר הלכה, להכריח להאמין בו כנבואה, אלא כגילוי מילתא בעלמא, וכל מי שאינו רוצה לסמוך עליו הרשות בידו, ולא הוי כמוותר על דברי נביא
A dream is only 'one sixtieth of prophecy', and so one is not forced to believe that they are true. He continues to quote from the Shita Mekubetzes to Bava Metzia: ברי חלומות הם, שהם קרובים לנבואה, אבל [לא] יסמכו בזה הענין, והחלומות שוא ידברו - dreams can be semi-prophetic, but they can also just be nonsense, and so a person makes a decision whether or not to follow the directive/halakha of the dream or not. Therefore, the teshuvos in Min Hashamayim aren't meant as clear revelations from Heaven, but as decisions made by the author to believe that his dreams were correct. This is also why other poskim felt perfectly comfortable arguing with the Shut Min Hashamayim if they felt that he was wrong.
I do not know what it says in the introduction of that book, however I would imagine that his explanation would go something like this.
The story of "Lo Bashamyim hi", exists in a very specific context. That context is a Beit Din arguing with one of the members of that Beit Din. That is, we have a situation, where a beit din is gathered, and they are making a ruling. In those contexts, the Shechinah is said to have descended upon the group. The Majority of that Beit Din are then given the authority to make a ruling, and Bat Kols are not a valid form of testimony to the beit Din.
However, the concept of "Lo Bashamayim hi", does not necessarily apply in a situation where there is no beit din, or there is no sanctioned method of testimony.
There are numerous examples in the Talmud, where a halacha is learned or passed down by eliyahu to a single individual, or through other form of knowledge gained from "the heavens". Never in any of those situations, do we argue "lo Bashamayim hi". The only time that argument is really made, or has any valdity is in a situation of a beit din, or a gathering and a strict vote, which is gathered from numerous talmid chachamim "sitting together" to discuss and come to a conclusion.
There are several Rishonim (collected in Encycolpedia Talmudis, but for example see the Raavid's comment on the Rambam Shofar Lulav V'Sukka 8:5 where he explicitly argues for his position because of Ruach HaKodesh - although he justifies it intellectually - see at the link the argument if the Raavid means it literally) that hold that the final Halacha is not like Rabbi Yehoshua, and in fact you can pasken from a Bas Kol.
After all, we see the argument between Beis Shammai and Beis Hillel was settled by a Bas Kol. (Not that there aren't other answers to that, but it is certainly a straight forward explanation). The Talmud itself suggests this as a possibility in Eruvin 6b-7a.