I think they first appeared in the 3e Epic Level Handbook. I don't recall them appearing in 2e.
Note we included one in Serpent Kingdoms (3.5e) as well.
Yes - it was in both those 3rd E books... I thought someplace someone put out a bunch of the new 3rd E creatures in old stats to make people happy. Cannot find it though.