All Maiar can make bodies at will. But nobody knows how long the process takes.
Do their spirits all go to a specific lace after their bodies are killed? Do their spirits stay where their bodies were killed until they decide to move to some other location?
Does it take seconds or hours or days or weeks or years or decades or centuries to make new bodies? In most cases it probably takes less than centuries.
There is some evidence that evil ainur and maiar lose their powers to make new bodies, which of course does not kill them since they were originally spirits without bodies.
In the First Age of the Sun Morgoth was trapped into his body and could not leave it or make another one or even modify it or heal the various wounds he suffered.
The bodies of various balrogs were killed in battle during the First Age, and one in the Third Age, and they did not instantly create new bodies within seconds to continue fighting their foes. This may be due to the normal time it takes a maiar to make a new body. But the fact that none of those balrogs is reported to have been active again in Middle-earth even years, decades, centuries, or millennia later indicates that something either prevented them from making new bodies or restricted them from using those new bodies in Middle-earth.
Sauron could make and unmake and change bodies at will for thousands of years, but when his body at the moment - which he had probably occupied for thousands of years as the ruler of Mordor and all of his followers - was killed during the downfall of Numenor he made a new body for himself within a few decades, if not much sooner, though the new body was black and ugly. After that body was killed it took him more than a thousand years to make a new body, and that body had a finger missing from one hand.
Thus we see a process of evil valar and maiar losing their powers to make new bodies at will. This may have been due to decrees of Eru and/or the natural results of their evil deeds.
But there is no direct statement about where in the universe the spirits of any or all of those maiar would now be, once they become almost totally incapable of affecting the material world of Arda in any way or doing anything more potent that suggesting evil thought and desires to people. After all, such maiar without any physical form would be almost totally incapable of doing anything which might be detected by men or even elves.
09/23/15 - As an example of how a maiar without a body would be almost undetectable in the physical world that included Middle-earth, suppose that the spirit of Sauron was at Aragorn's coronation and tried to get someone there to attack Aragorn, or Frodo, or Gandalf. I suppose that the spirit of Sauron could have put the idea of attacking someone into someone's head without their noticing it. But we all get odd impulses to do something evil from time to time and almost nobody ever acts on them, so unless Sauron picked someone there who already had a strong reason to attack Sauron's triumphant foes and was already almost at the point of doing so Sauron's suggestion would have just been shrugged off as a strange impulse by that person.
I don't think that Sauron would have been able to talk to any of the mortals there. Elves like Elrond and Legolas might have been better able to detect Sauron and talk to him if they wanted to - I don't imagine that it would have been a very polite conversation. And I think that Gandalf, a fellow maiar, though at the time incarnated in a merely Human body, would have been most likely to be able to detect Sauron and talk to him.
So if Sauron's spirit had been present for Aragorn's coronation it is possible that one of the hobbits might have noticed Elrond or Gandalf seeming to talk to himself, his lips moving as he telepathically told Sauron to go away, but would not have thought enough about it for it ever to have been mentioned in the Red Book.
So the question of where the spirits of evil maiar went after their physical bodies were destroyed and they could not make any new physical bodies would have been important to the other ainur whose natural state was pure spirits and who could interact with those evil bodyless maiar. But it would not matter much to elves and even less to men and dwarves and hobbits who lived in the physical world where spirits without bodies could do almost nothing that would ever get their attention, let alone have any influence on their lives.