Pattern matching Association in rules

The problem can be seen in simpler expressions:

MatchQ[<||>, <||>]
(* True *)

MatchQ[<||>, HoldPattern[<||>]]
(* False *)

This behaviour is inconvenient and could be classified as a bug, but...

We must take into account the fact that a constructed association object is an atom whereas the expression used to construct an association is not:

AtomQ[<||>]
(* True *)

AtomQ[Unevaluated @ <||>]
(* False *)

The behaviour we see is a consequence of this ambiguity in identical-looking forms that are structurally different.

Ambiguity of Association

On the one hand, Association can be used as a constructor function to build an association object:

Association[]

(* <||> *)

On the other hand, it serves as the symbolic head of a constructed association object:

Head[<||>]

(* Association *)

The difference between these two uses is normally hard to spot since the FullForm of a constructor expression is visually indistinguishable from the synthetic full-form of a constructed association object:

Hold[<|"a"->1,"b"->2|>] // FullForm

(* Hold[Association[Rule["a",1],Rule["b",2]]] *)

Hold[Evaluate @ <|"a"->1,"b"->2|>] // FullForm

(* Hold[Association[Rule["a",1],Rule["b",2]]] *)

But if we are careful, we can observe that the constructor form is a normal expression with subparts whereas a constructed association object is atomic:

Hold[<|"a"->1, "b"->2|>] /. _[e_] :> {Head[Unevaluated[e]], AtomQ[Unevaluated[e]]}

(* Association, False *)

Hold[Evaluate @ <|"a"->1,"b"->2|>] /. _[e_] :> {Head[Unevaluated[e]], AtomQ[Unevaluated[e]]}

(* Association, True *)

The analysis of cases like this can be quite complicated since many system functions have been hard-coded to make association objects appear like they are not atomic. But the simulation is not always perfect:

Hold[<|"a" -> 1|>][[1, 1]]

(* "a" -> 1 *)

Hold[Evaluate @ <|"a" -> 1|>][[1, 1]]

(* 1 *)

Indeed, this particular "imperfection" is by design.

Similar Problems Elsewhere

The behaviour we see will occur with any atomic object whose synthetic symbolic head has the same name as the constructor function. For example:

MatchQ[SparseArray[{1 -> 0}], HoldPattern[SparseArray[{1 -> 0}]]]

(* False *)

MatchQ[Graph[{1 -> 0}], HoldPattern[Graph[{1 -> 0}]]]

(* False *)

MatchQ[ByteArray[{1, 2, 3}], HoldPattern[ByteArray[{1, 2, 3}]]]

(* False *)

Atoms with apparent substructure violate the general principles of Mathematica. See, for example, discussions at (46850) or (6315899). The growing numbers of such atomic objects will cause this kind of problem to occur more often.

Associations Got Special Treatment

Note that in early releases of version 10, associations were completely opaque to the pattern-matching machinery. This caused some angst in the community (101898) since associations are now a fundamental data type, almost on par with lists. In later releases associations received special treatment with the pattern-matcher adjusted to be able to "see" into them. But the case at hand demonstrates that there are still cracks in the simulated subpart facade over the otherwise atomic associations.

Most other atomic types have not received such treatment, and remain opaque to the pattern-matcher.

Bug?

One could argue that we would have none of these problems if the construction expressions were different from the expressions that represent the constructed objects -- e.g. MakeAssociation vs Association. But we must also weigh this against the convenience of the short input form <|...|>. If we wanted a similarly short construction expression, we would need to come up with something that can be distinguished from the data form. Perhaps something ugly like <||...||>. Good luck explaining the difference to new users :) The design choice that was made simplifies the language syntax at the expense of the issues under discussion. On balance, it is a defensible choice.

To @WReach's examples, one can add these:

MatchQ[<||>, Unevaluated@<||>]
MatchQ[<||>, HoldPattern[Evaluate@<||>]]
(*
  False
  True
*)

It evidently has something to do with the first time an Assocation is evaluated. The following are typeset differently, Hold[#] &@<||> and Hold[<||>], depending on whether the association was evaluated:

The evaluated-association pattern, HoldPattern[Evaluate@<||>] or <||>, matches the evaluated association <||> in the OP's assocRuleList and is typeset as <||> instead of Association[].

One way to fix the OP's problem is to evaluate the associations in the patterns:

Cases[assocRuleList, HoldPattern[<||> :> _ // Evaluate]]
(*  {<||> :> "zero"}  *)

Cases[assocRuleList, HoldPattern[<|"a" -> 1|> :> _ // Evaluate]]
(*  {<|"a" -> 1|> :> "one"}  *)

RuleCondition gives another workaround:

Cases[assocRuleList, HoldPattern[<||> :> _] /. a_Association :> RuleCondition[a]]
(*  {<||> :> "zero"}  *)

Someone who knows the internal workings will have to explain the mechanics of what's going on and why there's a difference. It could be a bug as @WReach suggests. It's certainly confusing. HoldPattern[Evaluate[..]] seems a bit unfortunate.