What I finally had to do, was talk to a close friend who knows a lot of Mental Health practitioners, partly from using their services, partly from the fact this guy knows everyone in town. He was able to call a friend who is a retired Psychiatrist, who was able to help find someone who would take me without a referral, and further refer me to a good psychologist. There's also the issue that most insurance plans have pretty crappy coverage for this stuff. And since I can't get an in-network referral to an in-network doctor, I'll be paying for most of this out of pocket.
My advice, for the little it's worth, is first... Don't Give Up. It's a fucking absurd pain in the ass, but it is possible to overcome. Think about finding a doctor the same way you would about hiring an employee, that's basically what you're doing. Use your social network, do you know anyone who is in a high-risk group for depression or other mental health issues? It's likely you know someone who has struggled with this and just never said anything. Ask around. It sucks to have to reveal yourself that way, but it's really not as bad as it seems in one's imagination. You will probably be surprised how many people not only get it, but want to help. Try a doctor out, if he isn't working, fire his ass and get another. No different than hiring a contractor. It's easy to load a lot of emotion into the process, but avoid doing this and stick to business. And try not to get sucked into the psychiatry vs psychology wanking contest. They're different approaches, have different tools, and different efficacies for different issues. CBT is great for moderate depression. There's much less evidence it's helpful for ADHD. There's a whole class of medication that's quite effective for ADHD. There's much less evidence that zoloft and friends are useful long term for depression. Extrapolate that out for all the other possible mental health issue a person might have.
At any rate, you're not alone, my friend, and you're not the only one who has had to go thru this shit. It is possible... Email is in my profile, if you need someone to talk to, feel free to contact me. Best of luck.