Melkor came back from the void (above the Walls of Night) after he was expelled by Tulkas during the First Battle of All, and destroyed the Two Lamps. After that, he was again defeated in the Battle of Powers and locked in the Halls of Mandos.
I understand your confusion now. In Chapter 1 it is written that Melkor "passed therefore over the Walls of the Night with his host, and came to Middle-earth far in the north;". This, however, isn't the same Door of Night that seperated Arda from the Void, but rather a great mountain range that surrounded the land masses of Arda in the beginning. Melkor wasn't lurking in the Void, but in the uncharted wastes in the northern edges of the world. You can see from passages in the Silmarillion that the Door of Night was set in the "Walls of the World", at the "outermost rim of the world", and that you have to pass through Valinor to get there (Silmarillion, ch.24), whereas the Walls of the Night encircle the world, so that Melkor can pass over them and come to the North of Middle Earth (ibid, ch.1).
In the comments, you've brought a quote which seems to muddle the issue even further, referencing The Wall of Things and the Door of Night, but these are part of earlier drafts of the History of Middle Earth, and were revised and have not made it into the Silmarillion itself. The term "Wall of Things" does not appear in the Silmarillion at all.
After the Battle of the Powers, Melkor wasn't expelled from Arda:
(Silmarillion, p.60, Unwin Paperback edition, 1983).
So Melkor wasn't cast out after the Battle of the Powers, merely chained with Angainor and left to rot in the Halls of Mandos. And afterwards allowed to roam Valinor. It is only after the War of Wrath at the end of the First Age that he is cast beyond the Doors of Night, something that is considered irreversible.
It's interesting to note, though, that in some earlier versions of the story, Melkor does come back from the Void, at the very end of time. And a host of heroes from throughout history confronts him and his hosts, and Turin Turambar fells the great dragon Ancalagon that leads the charge. Of course, this doesn't mesh well with some other concepts, such as that Men don't really wait around for eternity like Elves do, so that's probably one reason it was scrapped.