First Point:
Please keep in mind that QS is a little like toolbar PR. Some of my most profitable keywords have a QS of POOR. I have spoken to an affiliate manager of a program that also has an inhouse staff to manage campaigns, and they agree this is very possible.
Second: Isn't QS tied to Keywords anyway?
I don't know about my account, but I know that when I start off with a brand new squeeky clean domain, the QS that I can only see as attached to my keywords, is usually very friendly.
If I use my oldest domain, and the one I used to use with Google with mediocre (awful) results, my QS starts off terminal.
As time passes with the newer domains, the keyword QS seems to fluctuate around day by day. Some of the QS drop, some maintain, but it looks pretty clearly tied to the keyword.
I guess you could even rehabilitate a domain, but it hardly seems worth it when domains are so cheap.
But really, get a cheap .info domain, and start a small adgroup with a few keywords and see what it looks like.
Also keep in mind that QS is partially out of your control. I have had it confirmed by Google reps that they also look at network performance. If nobody is generating clicks with certain keywords, you will start off damned.
The point? Most of us just start testing. Nobody here has a magic formula for getting cheap clicks. I sure don't, and I operate by paying more than most of you guys talk about. But in my main, niche that's just the way it is.