Here's a useful tip if you want to add new types of Fiends to your game and want the names to "match" the style in the Monster Manual, etc... Use a Latin dictionary! Many of the names for types of Fiends were created in just this way, by picking a decriptive Latin word and then adding a suffix to the end! An example: "Spinagon" is "Spina" (Latin for spined) + "gon" (beats me!). "Hydroloth" is "Hydro" (water) + "Loth" (for Yugoloth). This works for some Celestial races, too... "Leonal" is "Leon" (lion) + "al" (for Guardinal). You can have lots of fun making up new critters this way...
Creating Fiend names (and others!)
Quite a bit of it is also greek, like "hydro". It is true, though, that all the guardinals just have latin animal names. The modrons are of course called after latin numbers. On the other hand, most Tanar'ri and Baatezu have entirely fictional names, as have most other outsiders.
I mentioned "races" above, when the word I was looking for was "breeds": i.e. Spinagons are a breed of Baatezu...
Certain suffixes seen to be used over and over for certain types of fiends. For example, several Baatezu use the "-gon" suffix, serveral Tannari use the "-lith" suffix, and both types of fiend use "-zu". The Yugoloths, on the other hand, are uniformly "-loth"... (with the exception of a few new 'loths in the Fiend Folio and Monster Manual IV, but they don't have suffixes, so...) Likewise, Guardinals are all "-al"...
One note that I've always wanted to work into a campaign: Baatezu seem to have a pretty solid claim on the '-zu' suffix (barbazu, baatezu). Why, then, do glabrezu tanar'ri have the same ending? My idea was that those most vile tempters of the ambitious, the glabrezu, were once baatezu in the distant past, but betrayed the lawful fiends and changed sides, perhaps in return for the wish power which they now enjoy, given them by a Demon Prince who craved a way to lure new Blood War recruits into his horde.
I like it!
In Monster Manual II, there is at least one other Tannari with a "-zu" ending, so it's not just Glabrezu... I think "-zu" is actually common to both Baatezu and Tanarri, and Glabrezu don't have "-zu" affixed to their name as an insult or anything...
just shifting topic a bit, when naming new demon lords or devil nobles you could derive (and make it dificult but possible for clever players to see where you got them from) the names from modern film and writng since many of these have names from mythology.
Yeah, for instance a lesser-known appeliation for Hephaestus the Greek smith-god was "mulciber". You could use that as a Devil-smith's name, for example (maybe Mulciber makes magic weapons for Asmodeus). Lot of other gods and fiends in historical myth also have alternate names... and books LOADED with angel names to appropriate are likely in your local bookstore or library (both fallen and regular angels are listed in most such books...)
"A dictionary of Angels, including the Fallen Angels" is an excellent resourse for Celestial/Fiendish names, and included exhastive lists of fallen Angels and other evil spirits as well as good Angels and beings... the author is Gustav Davidz (not 100% sure on that last name)... if you use Celestials/Fiends heavily in your games, it is an invaluable resourse... it includes both Hebrew and non-Hebrew type names (but more of the former than the latter...)
Usually I take names of celebrities I happen to dislike and make anagrams out of 'em. Then you make anagrams out of those anagrams and add additional letters until they start to sound Lovecraft-ish...
A study of ancient world history can give a lot of inspiration for names in general. (Not just fiendish names, but it does include those, especially for the 'ancient eeevil' feel.)
BoGr Guide to Missile Combat:
1) Equip a bow or crossbow.
2) Roll a natural 1 on d20.
3) ?????
4) Profit!
I always have trouble coming up with names, particularly planar, because they're always so unusual. Not just celestial or fiendish names, but even people just living in the outer tend to have the most odd names. Cool, but very different from standard.
I just name fiends in my games after fiends I've met. Really adds to the verisimilitude.
Pants of the North!
This seems a much better method than the tried and true "throw a bunch of letters and some glottal stops into the name,'" like Zzyr'metog and A'brin'ogo or something stupid like that that just feels made up.
On a related note, I've always been pleased with a lot of dragon names. Especially the ones that not only describe the dragon, but shorten to another cool name: Couladremnos the Red, known as Cauldron to his friends .