how choosing the correct domain name is one of the most important things to have a successfull concept
Nonsense. The name is amongst the least important bits of almost any product. It should obviously meet some basic criteria (be pronouncable..). Beyond that it's mostly bikeshedding, unless you're in one of the rare markets/situations where branding really matters.
Moreover the tool you mention seems to be horribly misleading. It gives me a green "70%" in domain availability for a name that has .com, .net, .org taken...