Matching HoldPattern expressions

Clarification of HoldPattern usage:

HoldPattern[expr] is equivalent to expr for pattern matching, but maintains expr in an unevaluated form.

I think this can be ambiguous for beginners. One could think that what we are doing in

MatchQ[HoldPattern[a[1]], HoldPattern[_[_]]] 

is to more or less

MatchQ[ a[1], _[_] ] 

where both arguments are kept unevaluated. That's not the case. "for pattern matching" from the usage message means "when used in pattern". And here a pattern is the second argument.

Knowing that we can easily explain your examples:

---

So, case 1,

MatchQ[HoldPattern[a[1]], HoldPattern[_[_]]]

is really trying to match _[_] to HoldPattern[a[1]], with success because it really is (HoldPattern)[(a[1])].

Furthermore, it will fail to match a[_] because this represents an expression which outer head is a while it should be HoldPattern.

---

Case 2 can be explained this way too. When the HoldPattern is stripped, _[_][_] doesn't match HoldPattern[a[1][1]] as it really is _[_[_][_]]:

MatchQ[HoldPattern[a[1][1]], HoldPattern[_[_[_][_]]]]

True

---

Possible issues with Verbatim:

To prevent HoldPattern from being stripped you can use Verbatim. But it can't be used mindlessly. E.g. let's say you have defined:

a[_]:=2

This will create

HoldPattern[a[_]] :> 2

down value. As discussed your approach won't work:

MatchQ[ HoldPattern[a[_]] :> 2, HoldPattern[a[_]] :> 2 ] (*False*)

but also

MatchQ[ HoldPattern[a[_]] :> 2, Verbatim[HoldPattern][a[_]] :> 2 ]

fails because there isn't anything preventing a[_] from evaluating to 2.

Here we are safe:

MatchQ[
 HoldPattern[a[_]] :> 2,
 Verbatim[HoldPattern][a[_]] :> 2 // HoldPattern
]

---

The answer finally:

DeleteCases[
 values,
 _[a[1][__]] :> _ // HoldPattern
]

My go to method for handling *Values is to just use _ everywhere. So, I would use:

values = {HoldPattern[a[1][2]] :> 1, HoldPattern[a[2][3]] :> 5, 
    HoldPattern[a[1][x_, y_]] :> x + y, 
    HoldPattern[a[2][x_, y_]] :> x - y, HoldPattern[a[2][x_]] :> x};

DeleteCases[values, _[_[a[1][__]],_]]

{HoldPattern[a[2][3]] :> 5, HoldPattern[a[2][x_, y_]] :> x - y, HoldPattern[a[2][x_]] :> x}