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.
- Morgoth is thrust out of the universe through the doors of night, but will return one day. Whatever's going on, he isn't dead.
- Melian "vanished out of Middle-earth, and passed to the land of the Valar beyond the western sea, to muse upon her sorrows in the gardens of Lorien." She's not dead, either.
- Gandalf may well have actually died and (maybe) left Arda (I say "maybe" because the language is more poetic than precise) and seems to have been sent back by a special intervention of Iluvatar.
- Saruman? All we know is what the hobbits saw, which contains no privileged information.
- Sauron? We know that he survived, though disembodied and diminished.
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.