From what I have read on here it seems that there are mixed reviews on whether or not to use keywords in your name, such as software or games, since a Google search on your name with a popular keyword could put you at a disadvantage in page rankings as opposed to a more unique name.
Has anyone used any of the sites that say they will find a name for you for like $20 and had success?
You are going at it backwards. Conceptualize a set of overall image/brand "packages", then find ones that would resonate with you and with your target market. From that comes finding open domain names and such. Only then comes SEO.
Basic SEO (crawler-friendly, good keywords, appropriate home page text, etc...) that allows people specifically searching for you to find you is easy. Fighting your way up to the top of the iPhone game market in vapid Google searches requires SEO skills well beyond your abilities (or funds). Nightmares where companies create sites that are SEO-centered instead of user-centered abound. YEah, they may get to your domain, but then leave. This is the best SEO explanation I've ever read.
Also, I think too many people/companies put a disproportionate effort on SEO (perceiving as "easy" because you just have to line up keywords, etc.) versus a solid and broad branding and marketing campaign. (Which doesn't have to be complicated or costly, and which is much more important, esp. for startups. See guerilla marketing.)
You might get some ideas about the naming process from "The Igor Naming Guide to Creating Product and Company Names" which can be found here, for free.
You do need to be wary of using a name which is an actual word used in a different context because it might make searching for your business a bit like looking for a needle in a haystack.
Ultimately I wouldn't get too caught up on the name because you will give the name meaning by how good your product is, and you always have the option of renaming down the track once you have a clear direction.