I've modded this up because I'd like to hear what other hnusers have to say about this topic. I've just been through this process and it was very, very painful.

In the end way came up with a company name via a lot of lateral thinking. I spent a long time writing down all the attributes of our service and then trying to find related concepts and words and finally narrow down a list of hundreds of possibilities to a few possibles.

We then used purewhois.com to check domain names and uspto.gov to check trademarks.

We also involved everyone in the company in the process taking suggestions from everyone.