Yeah, my band agonized over this for quite awhile. We all really wanted to use the name "What The...?", but geez, how search-engine proof can you get? A lot of search engines won't even return ANY results on the words "What" or "The" because they're too comon so the search engine just throws them out.
Though funnily enough, if you type "The Who" into Google it DOES return mostly URL's about the band. There's probably a special database entry for them.
In the end we just decided fuck it, we'll use the name we want to use. I suppose it's better to have a name that's easily searchable, but whatever. I suggest searching on the names of band members, album titles or something else more likely to be found by search engines.