It's all speculation, and I thought for a time I would hold with
Maia as well for my personal opinion just for what that's worth.
We know many
Maiar came along with the
Valar to assist them.
There is no reason a Maia could not have 'fallen from his/her original task' and gone his/her own way, just as the
Istari (who were almost certainly Maiar) all did save
Gandalf. Perhaps that Maia could have taken on a 'bodily form', and remained therein. Hence,
Bombadil becomes.
It could equally be true that he is one of the '
spirits from afar' called by
Yavanna's thought at the awakening of the Firstborn "some of whom" dwelt in the olvar and telvar. (thus, not all of them did, yet they came.)
If that is the situation, this would likely put Bombadil more or less of the 'same age' as
Treebeard, who, being an Ent, was one of those such a 'called spirit' chose or was instructed to indwell.
There is a "charm" to considering Bombadil and Treebeard to be 'called spirits' of the same age and arriving at the same time.
But we still have the issue that Bombadil calls himself 'eldest' - a term never used, nor appropriate, to any Maia or spirit. Yet he may have used that term just for the benefit of his audience.
And
Elrond of Bombadil saying: "But I had forgotten Bombadil, if indeed this is still the same that walked the woods and
hills long ago, and
even then was older than the old. That was not then his name.
Iarwain Ben-adar we called him,
oldest and fatherless."
Then we have Gandalf calling Treebeard "the eldest and chief of the
Ents, and when you speak to him you will hear
the speech of the oldest of all living things." And of course
Celeborn called him "Eldest". Did that mean eldest of all as a term of honor, or just eldest of all those currently present as a term of honor? We do not know.
Additionally, Maiar and Spirits are never called "living things."
Of course, the existence of the
trees preceded the Firstborn and the Followers...
BUT Yavanna's thought called the spirits from afar "when the Children awake"... (another hard concept to pinpoint exactly because of other things said... but I will not enumerate as this whole thing is complex enough already.)
And we do have
the one member sharing that Christopher has said his father was given to use of such terms without really meaning or trying to indicate real 'specificity' or precise applicaition in their use. (My interpretation of the quotation given.) Thus... what did
Tolkien MEAN? Our crystal ball is cracked..!
At this time for me the 'weight of evidence' does not tip the scales in one direction or the other very much, and if/as it does, it is tipped toward the issue that neither can be either a Spirit or a Maia - and their relative
ages cannot logically or textually be deduced - thus I must leave the thing unresolved in my mind.
And I find I'm quite happy within myself with that conclusion as it turns out.