DanAbbamont - 3:52 am on Apr 6, 2011 (gmt 0)
The stuff that determines if your landing page, ads and keywords are "relevant" isn't all that sophisticated. Check out the official guidelines and suggestions and if you've made use of all of that info, you're probably good as far as that goes. Check out your competitors. If yours looks as "relevant" as theirs, it's probably just the nature of your niche and everyone is in the same boat.
What it sounds like is you're trying to build up a profitable campaign and expecting results too quickly. You want to spend a lot up front on split testing using ROI as your primary metric. You might find that out of two different ads, one with a lower quality score converts while one with a higher score doesn't. If you waste your time just trying to figure out what will give you the highest QS without extensively measuring results you'll lose out.
Now the most important part of developing your QS is having a good CTR. The more positive data Google has the better. You can keep bids low and build it, but this could end up taking a really long time. I've never done a campaign where I didn't just bid up to #1 at first. That way within a short period of time, you've collected enough data to see what your best ads / keywords / landing pages are so you can do some pruning. Then I'll let it operate in the red and watch the CTR data help the CPC drop and even out. After all that is settled, you can determine whether or not you're going to continue your campaign and if you do, you barely have to work on it other than routine maintenance.