Were you able to gain any insights into where the problem(s) might be using the keyword analysis tool (magnifying glass next to each keyword)? You can sometimes get a hint of what needs work by looking at that.
As for the text ad you\re using, does it include any or most of the keywords in your adgroup within it?
I don't mind taking a quick look at your current setup and structure to see if I can narrow down where your problem is. If you're up for that, just let me know...
While cases this extreme are thankfully not too common, they do happen. They most likely come with the complexity Google has of trying to automate the quality score via their algorithm vs. the next to impossible task of doing it manually via human editors.
No matter how good their algorithm gets, there are always going to be errors and exceptions that need to be made. So escalating the claim when you are certain something must be wrong is the way to go. If you don't get answers from the first person you speak with at Google, definitely go higher up to someone more experienced to resolve such issues.
We often intervene on behalf of our clients and from our experience, Google is generally quite responsive, but it can sometimes take talking to several people before you get clear answers or a solution to the problem. Unless you have dedicated reps at Google, you'll often speak with a less experienced junior person, so be patient, but firm in getting them or someone more experienced to properly answer your questions and look at your case individually.
That said, feel free to get in touch with me personally if you'd like a second opinion on such issues so you're better armed with the right info before calling the Adwords team. Knowing what to ask and where in your campaign to look will usually get you better answers and solutions a lot faster which translates to a higher ROI and minimal downtime. :)