First, a really good site to find available domain names is http://domai.nr/

They link to a bunch of registrars, but I do have the same question, which of those registrars are a reputable.