I don't know how long people have been coming up with odd names for groups of musical performers, but the practice dates back at least to the 1930s. (Before that there were named musical groups, but the names were usually descriptive (and often place-linked), like "The London Philharmonic Orchestra," rather than fanciful.) Bands with names like The Inkspots became increasingly popular in the '50s, and with the advent of rock 'n' roll the floodgates opened wide. Some band names, like The Beatles, were plays on words; others were references to works of literature, both obscure and well-known (I gather that the Grateful Dead briefly considered naming themselves "Hobbit"); others, like Country Joe and the Fish, were just mysterious. Eventually, groups began to intentionally choose names that would be considered offensive (a practice that proliferated in the punk scene), or that would prove problematic when spoken on the radio—from The Sex Pistols to Scraping Foetus Off The Wheel to The Butthole Surfers. And there are still plenty of band names that are just silly, such as John Trubee and the Ugly Janitors of America (whose sole LP was titled The Communists Are Coming to Kill Us).
Leviathan (the third book of the Illuminatus! trilogy) begins with a three-page list of (mostly imaginary) band names, including some of my favorites: The Senate and the People of Rome; King Kong and His Skull Island Dinosaurs; The Signifying Monkey; The Sound of One Hand; The Gospel According to Marx; Moses and Monotheism; The Thalidomide Babies; The Seven Types of Ambiguity; The Domino Theory; Maxwell and His Demons; Attila and His Huns; The Haymarket Bomb; The Blue Moonies; The Grassy Knoll; General Indefinite Wobble; Ms. and the Chairperson; Ahab and His Amputation; The Rosy-Fingered Dawn; The Wine-Dark Sea; The Snows of Yesteryear; MC Squared (a good rap name, don't you think?); Standard Oil of Ohio; The Heat Death of the Universe; The Horse of Another Color; The Deleted Expletive.
I occasionally come across phrases that I think would make good band names, but lacking a band, I have nothing to do with them but save them. My favorites so far are St. Vincent and the Grenadines, Bellyful of Dread, and The Slaughterhouse Five.
There's an automatic band-name generator on the Web; it's a little limited, but produces amusing Heavy Metal band names anyway, like Lion Maiden and Smoking Coma and Screaming Motor Head. These days it would probably be hard to come up with a catchy short phrase that hasn't been used as a band name at one time or another. In some cases the hardest part of forming a band is coming up with a name.... There are even songs about choosing a band name, such as the Bobs' "Naming the Band." If you're stuck for a name and the random names generator doesn't help, try this band names list.
I'm guessing the random band-name generator is of the "pick one item from column A and one from column B" variety; there are many examples of such random-item generators, including the automatic country-song generator and (not yet available in programmatic form) this action-movie title generator by Aaron Hertzmann (rearranged somewhat by me):
Aaron writes, "Take one word from the left column, and one from the right, find some aging but bankable stars, and you're ready to shoot your own summer flick!"
Finally, if you're all ready to start a high-tech company but you can't think of a name for it, pick any two to four syllables from this list and string them together (without spaces, and with intercalary capitals):