The Void

[Zigûr]

As usual, we can find interesting information, if not answers, in "Myths Transformed". In part (iii) of 'Notes on motives in the Silmarillion', Professor Tolkien defines the Void as "a conception of the state of Not-being, outside Creation or Eä":

the minds of Men (and even of the Elves) were inclined to confuse the 'Void', as a conception of the state of Not-being, outside Creation or Eä, with the conception of vast spaces within Eä, especially those conceived to lie all about the enisled 'Kingdom of Arda' (which we should probably call the Solar System).

Thus I think it's possible that it might be misleading to conceive of the true 'Void' as a place (as opposed to outer space, which was sometimes mistakenly called the Void). Thus Melkor 'searching the Void' might not be a physical activity but something more abstract.

I say this as someone who has always imaged Melkor striding about in the darkness looking for something he cannot find. If the Void is 'the state of Not-being', and as we know it is timeless ("the Timeless Void"), then I suspect its existence is more conceptual than physical - separation from Eru and the Flame Imperishable. I also suspect that it might be something arguably metaphysical because the Void is nothingness. There is nothingness (the Void) and there is "thingness" (Eru, the Timeless Halls and Eä).