Boldogs, Gothmogs and Sauron's New Clothes

[obloquy]

Ungoliante was an eala in her beginnings, yes, but other than that we know nothing about her. She came into Arda uninvited, and so does not fall into the categories of those who were stationed in Arda by Eru. The distinctions "Vala" and "Maia" are given to Ainur (which may itself be an Arda-specific class of beings) who occupy specific stations appointed to them by Eru.

Apart from this, she was never actually in Melkor's service, but that point is moot.

Edit: And it's a good thing the point is moot, because Tolkien disagrees with me. Here's his latest word on the subject from Annals of Aman:

Whence she came none of the Eldar know, but maybe she came to the South out of the darkness of Ëa, in that time when Melkor destroyed the lights of Illuin and Ormal, and because of his dwelling in the North the heed of the Valar was turned most thither and the South was long forgotten. Thence she crept towards the realm of the light of the Valar. For she hungered for light and hated it. In a deep cleft of the mountains she dwelt, and took shape as it were a spider of monstrous form, sucking up all such light as she could find, or that strayed over the walls of Valinor, and she spun it forth again in black webs of strangling gloom, until no light more could come to her abode, and she was famished.

It may well be that Melkor, if none other, knew of her being and her abode, and that she was in the beginning one of those that he had corrupted to his service.

Edit again: Reading more carefully reveals that Tolkien thinks she may have been one of those he corrupted to his service.