Evil minds become linked with hideous bodies
It would seem that both Melkor and Sauron lost the ability to assume a fair appearance once their spirit became so fixated on evil that their body could only do the same. In the case of Melkor, it (probably, see below) happened after the destruction of the Trees. For Sauron, it happened after the destruction of Númenor.
Nature of the Ainur
The relationship between the "spirit" (eäla) and "body" (hröa) of an Ainu is complex and, sometimes, unclear. The only two Ainur that were said to have lost the ability to appear in a particular form are Melkor and Sauron.
The Ainur are naturally disincarnate beings. They do not require a hröa to survive. Melkor, however, is the only Ainu to have become permanently incarnate. It was a consequence of disseminating his power throughout Arda:
To gain domination over Arda, Morgoth had let most of his being pass into the physical constituents of the Earth - hence all things that were born on Earth and lived on and by it, beasts or plants or incarnate spirits, were liable to be 'stained'.
Morgoth at the time of the War of the Jewels had become permanently 'incarnate': for this reason he was afraid, and waged the war almost entirely by means of devices, or of subordinates and dominated creatures.
[...] When that body was destroyed he was weak and utterly 'houseless', and for that time at a loss and 'unanchored' as it were. We read that he was then thrust out into the Void.
The History of Middle-Earth Volume 10: Morgoth's Ring, Myths Transformed, pp. 394-395
Amount of control on appearance
The "natural" physical appearance of the Ainur seems to be based on their personality:
Their forms were thus expressions of their persons, powers, and loves. They need not be anthropomorphic (Yavanna wife of Aulë would, for instance, appear in the form of a great Tree.) But the 'habitual' shapes of the Valar, when visible or clothed, were anthropomorphic, because of their intense concern with Elves and Men.
The Letters of J.R.R. Tolkien, #212 Draft of a continuation of the above letter (not sent), p. 285
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.
The Silmarillion, Ainulindalë, p. 11
It also would appear that Melkor could not wholly control his appearance, since the state of his mind had an effect on it:
Much could thus 'go on behind Manwe's back': indeed the innermost being of all other minds, great and small, was hidden from him. And with regard to the Enemy, Melkor, in particular, he could not penetrate by distant mind-sight his thought and purposes, since Melkor remained in a fixed and powerful will to withhold his mind: which physically expressed took shape in the darkness and shadows that surrounded him.
The History of Middle-Earth Volume 10: Morgoth's Ring, Myths Transformed, pp. 399
Whether this only applies to Melkor is unclear. It might also have to do with his being permanently incarnate.
It also seems like the Ainur become used to their body, making it difficult to change to another one:
It is said that the longer and the more the same hröa is used, the greater is the bond of habit, and the less do the 'self-arrayed' desire to leave it. As raiment may soon cease to be adornment, and becomes (as is said in the tongues of both Elves and Men) a 'habit', a customary garb. Or if among Elves and Men it be worn to mitigate heat or cold, it soon makes the
clad body less able to endure these things when naked
Ósanwe-kenta, Note 5
Melkor's last appearance change
Now Melkor came to Avathar and sought her out; and he put on again the form that he had worn as the tyrant of Utumno: a dark Lord, tall and terrible. In that form he remained ever after.
The Silmarillion, Of the Darkening of Valinor, p. 77
This quote asserts that Melkor would never change form after the destruction of the Trees. However, in The Tale of Adanel, Andreth talks about the early history of Men, who woke up after these events:
Some say the Disaster happened at the beginning of the history of our people, before any had yet died. [...] [One] appeared among us, in our own form visible, but greater and more beautiful; and he said that he had come out of pity. [...] [He] was clad in raiment that shone like silver and gold, and he had a crown on his head, and gems in his hair.
Then he came again, walking through the shadow like a bright fire. [...] but he seldom appeared among us again in fair form, and he brought few gifts.
The History of Middle-Earth Volume 10: Morgoth's Ring, Athrabeth Finrod ah Andreth, pp. 345-347
In the text, Andreth never mentions the name of the being, only describing it as "The Voice". It is commonly assumed to refer to Melkor, but it could someone else, such as Sauron. Assuming it is Melkor, there is a discrepancy between The Silmarillion and this particular text.
In the Ósanwe-kenta, it is said that "in the end", Melkor had no control over his form:
[...] he became in the end, in himself and without their support, a weakened thing, consumed by hate and unable to restore himself from the state into which he had fallen. Even his visible form he could no longer master, so that its hideousness could not any longer be masked, and it showed forth the evil of his mind.
Ósanwe-kenta, Note 5
The exact time "the end" represents is unclear. If we assume that it was Melkor who appeared to Men when they awoke, then his ability to change form must have been lost sometime during the 590 years that followed, until the War of Wrath.
If Melkor wasn't "The Voice", then there is no discrepancy. It would be surprising to me, however, that Melkor would have sent a servant, even his best, for such as task as corrupting the Father of Men.
Sauron is never said to have lost his ability to change forms at will. However, he seems to be restricted on which form he could assume:
But Sauron was not of mortal flesh, and though he was robbed now of that shape in which he had wrought so great an evil, so that he could never again appear fair to the eyes of Men [...] [He] dwelt there, dark and silent, until he wrought himself a new guise, an image of malice and hatred made
The Silmarillion, The Akallabêth, p. 336
It seems clear to me that he could still create a body for himself, but that he had no control on its appearance. Strictly speaking, in fact, it would seem that it only applied to Men, but I do not think this was the intention.
Fixation of evil spirits
In a discussion of spirits and their ability to heal, Tolkien talks about evil spirits and their fixation on evil deeds, even to the point of self-destruction:
The Elves certainly held and taught that fear or 'spirits' may grow of their own life (independently of the body), even as they may be hurt and healed, be diminished and renewed. If they do not sink below a certain level.
Since no fea can be annihilated, reduced to zero or not-existing, it is not clear what is meant. Thus Sauron was said to have fallen below the point of ever recovering, though he had previously recovered.
What is probably meant is that a 'wicked' spirit becomes fixed in a certain desire or ambition, and if it cannot repent then this desire becomes virtually its whole being. But the desire may be wholly beyond the weakness it has fallen to, and it will then be unable to withdraw its attention from the unobtainable desire, even to attend to itself. It will then remain for ever in impotent desire or memory of desire.
The History of Middle-Earth Volume 10: Morgoth's Ring, Myths Transformed, pp. 404, including note #11 pp. 407-408
In the Ósanwe-kenta, it is said that evil spirits sometimes became inextricably linked to evil-looking bodies:
[Melkor and some of his greatest servants] became wedded to the forms of their evil deeds, and if these bodies were taken from them or destroyed, they were nullified, until they had rebuilt a semblance of their former habitations, with which they could continue the evil courses in which they had become fixed.
Ósanwe-kenta, Note 5