have you guys had the same issue before? do you just give up and pick any random available domain?! How important is it for your domain name to be related to the service you are offering?
Finding a domain name that is available, memorable, easy to spell, snappy AND which quickly gets the idea behind your product/service across is HARD but my advice is to persevere with it. A good domain name makes a big difference when it comes to user traction and seo (and, for me, just feels better than inventing some random name that bears no relation to the site).
A lot of the time I find the .com is taken (but not being used) and the .net is free. So I register the .net and then try and pounce on the .com when it comes up for renewal (this is an art in itself). If the .com gets renewed I occasionally (depending on how badly I want it) approach the owner and ask if they'll sell it (be warned some people have ridiculous ideas of how much a domain is worth).
An alternative is to try extensions other than .com (examples: .io .in .is .to). This is what pinboard.in did and I think it works (pinboard is easy to spell, memorable, snappy and does a good job of explaining what the site does). I use www.eurodns.com when searching for weird domain extensions (as you can check virtually all of them in one go).
Failing all of that, get a thesaurus, dictionary and a few bottles of wine and just lock yourself in a room until something clicks!
cheers