Sauron and Gandalf both suffer physical deaths (Sauron at least twice) but do not return to the halls of Mandos for recovery, but Saruman dies and is then impotent, forbidden to return and will never again take form. Melian dies of grief and goes back to Mandos.
So what's the deal? What are the rules on reembodement for the Ainur?
Reincarnation occurring from the halls of Mandos seems to be a thing only for elves, and the single exceptional case of Beren (exceptions like this actually have to be effected personally by God/Eru).
The Ainur are at a fundamental level immortal, in the sense that their spirits (fëar) cannot be destroyed, and are bound to the world and cannot leave it (setting aside exceptions). However, in this sense, elves are also "immortal".
The difference between elves and Ainur seems to lie in how their spirits interact with bodies.
An elf is born with with one body associated with its spirit, and never has the ability to recreate this body after it is destroyed. This is why elf spirits have to go to the halls of Mandos to get reincarnated.
The Ainur were not originally embodied, but they have the ability to fashion bodies for themselves of their own design. However, even when they create a body like this, they are not (or at least, not always) "incarnate" in the same way as the elves; they are generally described with the analogy of wearing their bodies like clothing or "raiment".
There are complications to this. The Ainur do not have unlimited reserves of "power" to influence the world. Their bodies are part of the physical world and can be destroyed, and the loss of something that they have invested significant power into making may represent a permanent loss of power. (There are many examples in Tolkien's work of this concept. Sauron didn't actually die when the One Ring was destroyed, but his chance at exerting power effectively was permanently broken because he could not recover the power he had put into it. The Two Trees were made by the Valar, but they couldn't just re-make them after they were destroyed: they had already expended that power.)
Also, it seems their forms may become considerably more "fixed" than the clothing analogy implies, although the exact reasons for this aren't completely clear to me. I think it is discussed in the "Osanwe-kenta", Note 5. Melian in particular was subject to this because she bore a child.
That said, I haven't found any source that says that Melian died even in the limited sense of having her physical body destroyed; she may have simply returned to Valinor in her body when her husband died. But the text seems to be a bit vague. For example, Tolkien Gateway says
Thingol's arrogance eventually resulted to his death in the Battle of the Thousand Caves. Melian then vanished from the mortal lands, passing to Valinor, where she mourned the loss of her husband in the Halls of Mandos and her daughter to the unknown fate of the Gift of Men.
The Halls of Mandos were a physical location in Valinor, although the living are not allowed to visit (according to the answer to this question: How do the dead in the Halls of Mandos exist alongside the living elves in the Valinor?).
Related questions:
How many of the Ainur were unable to change their physical form?
Other than Morgoth, were any of the Valar ever susceptible to physical injury?
Related discussion on another website:
The wizards/Istari are another kind of special case: in some not clearly defined way, they were actually placed in "incarnate" human bodies capable of real death. (I feel vaguely like referencing the issue of the nature of Jesus' incarnation, which famously is the topic of a number of Christian heterodoxies and heresies. Explaining this kind of thing is complicated, and I don't think Tolkien ever gave us a good explanation of how it works in his world.) Unfortunately, I don't think Tolkien makes it clear whether their "real" death is like the death of humans (which, due to the inescapable gift of Eru, involves passing out of the world) or that of elves (which just involves separating from the body).
Gandalf was brought back from death by a direct act of God, another exception.
What happened to Saruman upon his death isn't clearly spelled out, as far as I know. I don't think it is made clear whether he suffers the fate of a Man (being sent out of this world) or of an Elf (being sent to the halls of Mandos, and not being allowed to reincarnate because he was evil) but my impression is that it was the former.
Related questions about the Istari:
What exactly happened to Gandalf's spirit after he "died" fighting the Balrog?
Did Saruman continue to exist as an ethereal Maiar after he was murdered?
Is Gandalf the Gray's power actually limited or did he merely promise to not use it?
What would happen if an Istar broke the Valar's rule but saved Middle Earth anyway?
There's a lot to be said for @sumelic's answer, but I believe that it generalizes too much from too little data.
First, Men and Elves (and maybe the Dwarves) go to Mandos when they die. Men's spirits spend a time in Mandos and then go beyond the world to an unknown fate. Elves are immortal within the world and most reincarnate in some unspecified fashion.
The Silmarillion says:
For the Elves die not till the world dies, unless they are slain or waste in grief (and to both these seeming deaths they are subject); neither does age subdue their strength, unless one grow weary of ten thousand centuries; and dying they are gathered to the halls of Mandos in Valinor, whence they may in time return.
Two additional passages from the Silmarillion also support this conclusion:
For though Eru appointed to you to die not in Eä, and no sickness may assail you, yet slain ye may be, and slain ye shall be by weapon and by torment and by grief; and your houseless spirits shall come then to Mandos. There long shall ye abide and yearn for your bodies, and find little pity though all whom ye have slain should entreat for you.
It doesn't make sense to talk about finding little pity for being stuck in Mandos unless pity is to be hoped for and escape is possible. More clearly, after Faenor dies, Tolkien shows the completeness of his fall by saying that
his likeness has never again appeared in Arda, neither has his spirit left the halls of Mandos.
which makes no sense at all unless his likeness appearing again in Arda and his spirit leaving Mandos would be expected. If permanent residence in Mandos is the fate of Elves on death, it would make no sense at all for the narration to single Feanor out for this punishment for the enormities he committed.
But with a single exception, we have even less information about what happens to Maiar and Valar after their bodies are destroyed. The problem is that -- again with that single exception -- each being's fate is different.
That's it. That's all the data we have.
The exception I mentioned above, of course, is what happened to Sauron, Morgoth and (I believe) Saruman: The practice of evil, the seeking of domination over the physical world, requires one to "spend" one's own being on the project. Sauron poured his own power -- part of made him himself -- into the Ring. Tolkien's notes suggest that Morgoth did likewise in the marring of all of Arda.
The consequence of this spending one's own being is a diminishment: At first, Morgoth and Sauron simply become unable to create false "fair" bodies for themselves. They are still Ainur, but diminished.
Sauron (still able to appear to Celebrimbor and the Elves of Eregion as a trustworthy and wise Ainur) pours his being into the Ring and after the fall of Numenor, flees back to Middle-Earth and creates a new body, but finds he can no longer create a fair one. And when that body is destroyed by Elendil (even though the Ring remains) he is bodiless for thousands of years. His practice of evil and domination takes something out of him. Eventually he returns to a body and when the Ring itself is destroyed and Barad-dur falls and that latest body is destroyed, he is no longer able to create a new one.
For he will lose the best part of the strength that was native to him in his beginning, and all that was made or begun with that power will crumble, and he will be maimed for ever, becoming a mere spirit of malice that gnaws itself in the shadows, but cannot again grow or take shape.
And I believe that what the Hobbits saw at Bag End when Wormtongue stabbed Saruman:
...about the body of Saruman a grey mist gathered, and rising slowly to a great height like smoke from a fire, as a pale shrouded figure it loomed over the Hill. For a moment it wavered, looking to the West; but out of the West came a cold wind, and it bent away, and with a sigh dissolved into nothing.
is significantly close to what happened after Sauron fell:
And as the Captains gazed south to the Land of Mordor, it seemed to them that, black against the pall of cloud, there rose a huge shape of shadow, impenetrable, lightning-crowned, filling all the sky. Enormous it reared above the world, and stretched out towards them a vast threatening hand, terrible but impotent: for even as it leaned over them, a great wind took it, and it was all blown away, and passed; and then a hush fell.
and strongly supports the answer that the fates of Sauron and Saruman are the same. That when Maiar have so spent their being that they can no longer put on a body, they remain "a mere spirit of malice that gnaws itself in the shadows, but cannot again grow or take shape."
There's one final piece of evidence to consider:
Now the Valar took to themselves shape and hue; and because they were drawn into the World by love of the Children of Iluvatar, for whom they hoped, they took shape after that manner which they had beheld in the Vision of Iluvatar, save only in majesty and splendour. Moreover their shape comes of their knowledge of the visible World, rather than of the World itself; and they need it not, save only as we use raiment, and yet we may be naked and suffer no loss of our being. Therefore the Valar may walk, if they will, unclad, and then even the Eldar cannot clearly perceive them, though they be present. But when they desire to clothe themselves the Valar take upon them forms some as of male and some as of female; for that difference of temper they had even from their beginning, and it is but bodied forth in the choice of each, not made by the choice, even as with us male and female may be shown by the raiment but is not made thereby. But the shapes wherein the Great Ones array themselves are not at all times like to the shapes of the kings and queens of the Children of Iluvatar; for at times they may clothe themselves in their own thought, made visible in forms of majesty and dread.
When you think of an Ainur's body, think of a human's clothes. If the Ainur are unmarred, the destruction of a body may be embarrassing, but is hardly fatal.
So, bottom line: There is no evidence that the Ainur need Mandos to recreate their bodies. Their bodies are not essential to their being, anyway. As long as their being is not diminished through their own (bad) actions, they can walk as they choose, clad or unclad. It's only after they spend themselves on evil that they lose that ability.
Beyond that, we don't have enough information to do more than speculate.
