It's a pain the neck that is for sure!

Try Swahili (East Africa) names, they sound good rolling off the tongue. My steps have always been: Domain Check, Search Name on Internet with Combos, Trademark "word mark." If you can get past all of that, then you need to check for the logo design trademark search. Really, the wordmark is quite important. BUT....another important step now in my opinion is checking for all the Twitter and Facebook URL's too. Trying to brand that one domain with everything... makes it pretty tough huh?

If the domain is not available I move on, else go to the next steps.

I spent 4-6 months trying to come up with a name, but I suppose its different for everyone.