[Eldy]

I have a similar take on Bombadil, though I don't think he's necessarily a Maia. That's certainly one possibility: the Valaquenta is explicit that there were Maiar in Middle-earth, and implies that this was a majority ("few have names in any of the tongues of the Children of Ilúvatar; for though it is otherwise in Aman, in Middle-earth the Maiar have seldom appeared in form visible to Elves and Men"). But he could be an Ainu or some other sort of spirit who was not one of the Maiar. To again quote from the Valaquenta:

Among them [the Valar] Nine were of chief power and reverence; but one is removed from their number, and Eight remain, the Aratar, the High Ones of Arda: Manwë and Varda, Ulmo, Yavanna and Aulë, Mandos, Nienna, and Oromë. Though Manwë is their King and holds their allegiance under Eru, in majesty they are peers, surpassing beyond compare all others, whether of the Valar and the Maiar, or of any other order that Ilúvatar has sent into Eä.

The key phrase here is "any other order that Ilúvatar has sent into Eä". In the early phases of the mythology, especially The Book of Lost Tales, there were references to many different classes of spirits, including "brownies, fays, pixies, [and] leprawns", which Tolkien was clear to distinguish from the Eldar (HoMe I, The Coming of the Valar). The idea of there being many different orders of spirits was most clearly present in the Book of Lost Tales period, when we know they were "brownies, fays, pixies, [and] leprawns" which were clearly distinguished from the Eldar (HoMe I, The Coming of the Valar). However, most vaguely defined spirits of the early mythology were subsumed into the catch-all category of Maiar in the early 1950s when Tolkien was reworking the Annals of Valinor into the Annals of Aman (a process documented in HoMe X). The interesting thing about the "any other order" line from the published Valaquenta, though, is that it's source is from the same time period as the introduction of the Maiar, some thirty years after the Lost Tales (HoMe X, The Later Quenta Silmarillion, Of the Valar):

Thus it may be seen that there are nine Valar, and Seven queens of the Valar of no less might; for whereas Melkor and Ulmo dwell alone, so also doth Nienna, while Estë is not numbered among the Rulers. But the Seven Great Ones of the Realm of Arda are Manwë and Melkor, Varda, Ulmo, Yavanna, Aulë, and Nienna; for though Manwë is their chief [> king], in majesty they are peers, surpassing beyond compare all others whether of the Valar and their kin, or of any other order that Ilúvatar has conceived [> caused to be].

My interpretation is that this refers to Ainur who entered Arda but were not considered part of the Valar or Maiar, though other possibilities exist (which are not necessarily mutually exclusive). Aside from Tom, we have several other mysterious beings whose origins potentially lie here. Ungoliant is one, as Inziladun points out. So are the "nameless things" beneath Moria (TTT, III 5):

‘Deep is the abyss that is spanned by Durin’s Bridge, and none has measured it,’ said Gimli.

‘Yet it has a bottom, beyond light and knowledge,’ said Gandalf. ‘Thither I came at last, to the uttermost foundations of stone. He was with me still. His fire was quenched, but now he was a thing of slime, stronger than a strangling snake.

‘We fought far under the living earth, where time is not counted. Ever he clutched me, and ever I hewed him, till at last he fled into dark tunnels. They were not made by Durin’s folk, Gimli son of Glóin. Far, far below the deepest delvings of the Dwarves, the world is gnawed by nameless things. Even Sauron knows them not. They are older than he. Now I have walked there, but I will bring no report to darken the light of day. In that despair my enemy was my only hope, and I pursued him, clutching at his heel. Thus he brought me back at last to the secret ways of Khazad-dûm: too well he knew them all. Ever up now we went, until we came to the Endless Stair.’

Perhaps the most intriguing thing here is that the "nameless things" are stated to be older than Sauron. On the face of it this seems impossible; Sauron (as an Ainu) existed before the creation of the physical universe or even time itself, and so would seem to be older than anything in Eä. But we get another clue in the discussion of Caradhras and whether the mountain itself was sentient and responsible for the Fellowship's hardship when attempting to traverse it (FOTR, II 3):

‘We cannot go further tonight,’ said Boromir. ‘Let those call it the wind who will; there are fell voices on the air; and these stones are aimed at us.’

‘I do call it the wind,’ said Aragorn. ‘But that does not make what you say untrue. There are many evil and unfriendly things in the world that have little love for those that go on two legs, and yet are not in league with Sauron, but have purposes of their own. Some have been in this world longer than he.’

I think that "world" in this context needs to be interpreted not as the Planet Earth, but in a more general (or perhaps metaphysical) sense as the physical universe. The Valar and Maiar were responsible for the shaping of Eä but did not initially create it. The implication is (in my opinion) that there were already beings or entities of some sort in Eä before the Valar and Maiar entered into it. What they were specifically ... who knows. The mystery is kind of the point. "Echoes of the music of the Ainur" is one idea I've seen floated, though, and I think it's as good a guess as any.

To tie things back to Bombadil, some people interpret his statement that he was "was here before the river and the trees; Tom remembers the first raindrop and the first acorn.... He knew the dark under the stars when it was fearless – before the Dark Lord came from Outside" to mean that he must have predated the arrival of the Ainur (including Melkor). However, landmasses, weather systems, and flora did not yet exist when the Ainur arrived: "when the Valar entered into Eä they were at first astounded and at a loss, for it was as if naught was yet made which they had seen in vision, and all was but on point to begin and yet unshaped, and it was dark" (TS, Ainulindalë). Also, Melkor wasn't a Dark Lord yet, and I think Bombadil was almost certainly referring to Melkor's return to Arda, minions in tow, as described in the chapter "Of the Beginning of Days".