I drafted this answer many days ago but did not complete it. My intention is to define red flag notice. However, I'm hitting Submit because I think it's a good question and hope this will inspire other answers.
It seems like your immediate question, regarding the DCMA notices which Google is forwarding, is not a legal question. It is a question that can only be answered by Google and is dependent on their practices. Frankly though, it seems to me that Google search results might not be important based on the purpose of your proxy service. However perhaps your user base has evolved.
You are a service provider under 17 USC 512(k)(i). If you aren't we need to clear that up!
As for the copyright holders, you haven't received notice complying with 17 USC 512 (c)(3)(A)(i-iv). As such you don't have notice.
Even if these notices don't qualify then we argue about whether you have red flag notice - based on facts and circumstances. (See Grokster)
EDIT TO ADD:
17 U.S. Code § 512 - Limitations on liability relating to material online is one of the sections created by the DMCA. It is sometimes referred to as the safe harbor. You can read about it on Wikipedia® page for the Online Copyright Infringement Liability Limitation Act.
If you read that Wikipedia® page you will see a short section on Red Flags. They say it as well as I could:
[In addition to notice from a copyright holder, the second way] that an OSP can be put on notice that its system
contains infringing material, for purposes of section 512(d), is
referred to the "red flag" test. The "red flag" test stems from
the language in the statute that requires that an OSP not be “aware of
facts or circumstances from which infringing activity is apparent.”
The "red flag" test contains both a subjective and an objective
element. Subjectively, the OSP must have knowledge that the material
resides on its system. Objectively, the "infringing activity would
have been apparent to a reasonable person operating under the same or
similar circumstances."
The reason that notice is important is that the safe harbor provided is only available if you do not know that infringing is happening. Plaintiff's prove knowledge through the letter or through red flags.
I am glad that you asked about Grokster, because that was the wrong case! The case to look at is Viacom Int'l, Inc. v. Youtube, Inc., 676 F.3d 19, (2nd Cir., 2012).
The difference between actual and red flag knowledge is thus not
between specific and generalized knowledge, but instead between a
subjective and an objective standard. In other words, the actual
knowledge provision turns on whether the provider actually or
“subjectively” knew of specific infringement, while the red flag
provision turns on whether the provider was subjectively aware of
facts that would have made the specific infringement “objectively”
obvious to a reasonable person. The red flag provision, because it
incorporates an objective standard, is not swallowed up by the actual
knowledge provision under our construction of the § 512(c) safe
harbor. Both provisions do independent work, and both apply only to
specific instances of infringement.
In other words, you lose your safe harbor protection if you know of facts and circumstances that would lead an ordinary person to know that infringement is happening.
So the question for you is - do the letters forwarded by Google mean that you have knowledge and are outside of the safe harbor? Well that's the question that lawyers fight about! In fact Columbia Pictures Indus., Inc. v. Fung, 710 F.3d 1020 (9th Cir., 2013) is all about that fight. If you read that case you will see that Fung was doing a bunch of shit that totally made it completely obvious that he was infringing. And he was earning money directly from it. He was screwed from the start.
Now again, this does not really help you with the google blacklist problem, but it should help you understand what you need to do as a service provider to not be complicit in copryright infringement.
You really should read the Fung case and 17 U.S.C. § 512 - they will go a long way to help you understand the analysis a court will apply.
EDIT
Regarding your legal exposure, I always assume that a cease and desist letter will precede a lawsuit. With that said, only you know how much infringing is coming across your server. Fung made his money directly from the infringement. He attracted website visitors specifically because of the infringement. He had emails and other documents proving this.
Diebold is interesting because they attempted to use copyright to control the spread of their emails. First the court said no commercial harm and no diminishment of value of the works. Then the court found that the stuff wasn't even subject to copyright. This is obviously not a typical case. But it sounds like you see yourself as OPG in this case. I don't see how you can become a plaintiff against bona fide copyright holders who follow the links as far as your server. As I understand it, you are a reasonable target of the the notices, that's the result of running the proxy. However, I might be getting out of my technical depth here.
As I intimated earlier, you might need to seek out some strategic advice regarding dealing with Google and the specific steps you might take to stay in the right side of their enforcement.
