The fact that the names you've come up with exist in other states doesn't necessarily preclude you from registering the name AS A BUSINESS NAME in your own state, if it's clear there. BUT, if you plan, as many if not most businesses do, to 1) use your business name AS your TRADEMARK (these are different animals with different functions) and 2) expand your business across state lines OR if these guys already have a presence in your state/area OR if their names are federally registered as trademarks, then you really need to sit up and take note. Are these other businesses selling similar goods or services to yours? And how distinctive is the name at issue? The bottom line for trademarks is you don't want to get your customers confused as to the source of the services/goods you offer, i.e. is there a "likelihood of confusion". Will they think you're connected to another business? Will they mistake your goods for hers? Will they think his services are yours?
Ideally, for the best protection, you'll want to come up with a unique name for yourself. Could be made-up words (that is, "fanciful", think of "Xerox") or words that are "totally random", as the kids say, when applied to your product/services (called "arbitrary", think of "Apple" for computers.) Another approach is to use a "suggestive" name -- perhaps a clever rhyming or alliterative way to refer to what you do or sell. Avoid names that seem to just outright describe the goods or services, though. These take a lot of proving up to show you've developed trademark rights in them over long years of use, thus acquiring what's called "secondary meaning" as a mark. (And for federal registration, descriptive names have to sit 5 years on the supplemental register.) Of course, the generic term for the goods or service can't be monopolized by just one business and so is off limits.
Once you come up with several names which you think may be good contenders, then do see a proper trademark attorney who can run a more extensive search for other uses of your proposed mark and analyze the results--e.g., "yes, here's a similar name but it's for widgets and you're selling tanning spa services." -- and help you weigh the pros and cons of the various choices. (While the attorney might be willing to work with your own search results, s/he'll probably want to do a search s/he controls, to make sure it's done right.) Also note that use on the net may be, I believe, subject to a broader interpretation of "likely confusion" than the traditional trademark analysis.
Can I search some data base for licensed names or trademarks that I can not legally use?
Because of all the hoopla over "licensed" products, there a misconception that the license is some special governmental category, or imprimatur. A license in the trademark sense is a just a contract of permission. It's the contract whereby the trademark owner lets someone else use the trademark under certain circumstances. (Trademark owners MUST keep some control over how their mark is used, or the mark doesn't mean anything and can be lost.) The license has to be based on existing trademark rights. So the category "licensed" marks is just a sub-category of trademarks generally.