Association's Attributes change between 10.3.1 & 10.4?

One significant difference is the following

In version 10.3.1

a = 3;
Association[Unevaluated[a -> 2]][Unevaluated[a]]

2

In version 11.0.1

a = 3;
Association[Unevaluated[a -> 2]][Unevaluated[a]]

Association[Unevaluated[a->2]][Unevaluated[a]]

In version 11.0.1 (clearing attributes)

Unprotect[Association];
ClearAttributes[Association, HoldAllComplete];
a = 3;
Association[Unevaluated[a -> 2]][Unevaluated[a]]
SetAttributes[Association, HoldAllComplete];

Missing[KeyAbsent,3] 
(*should be interpreted as Missing[KeyAbsent, a], as 3 is actually a valid key here*)

I see this change as a reminder that that Association is not meant to be used like this (with keys that are "unstable"/unevaluated). In this answer, taliesin says: "But generally this just sounds like a dangerous and confusing game to play, to me". There have been good arguments against using Association like this, like the fact that if you Compress and Uncompress an Association, it would evaluate its keys.

Interestingly it is still possible to create a broken association in 11.0.1, which may be a bug of PositionIndex.

a = "Fail!";
p = PositionIndex[Unevaluated[{a, b, c, d}]]
Uncompress@Compress@p

<|a->{1},b->{2},c->{3},d->{4}|>
<|Fail!->{1},b->{2},c->{3},d->{4}|>

An aspect of the difference is that in versions newer than 10.4, evaluation takes place "behind the scenes". This explains the shorter traces in mikado's answer.

In version 10.3.1

Trace[Association[1 + 1 -> 2]]

{{{1+1,2},2->2,2->2},Association[2->2],<|2->2|>}

In version 11.0.1

Trace[Association[1 + 1 -> 2]]
Trace[Association[1 + 1 -> 2], TraceInternal -> True]

{Association[1+1->2],<|2->2|>}
{Association[1+1->2],{{{1+1,2},2->2,2->2},{2->2}},<|2->2|>}

We can investigate the difference in behaviours using ClearAttributes and SetAttributes. One apparently minor benefit of setting HoldAllComplete is simpler Trace expressions.

ClearAttributes[Association, HoldAllComplete];
Trace[Association[a -> 1, b -> 2]] // Length
(* 4 *)

SetAttributes[Association, HoldAllComplete];
Trace[Association[a -> 1, b -> 2]] // Length
(* 2 *)

I've not been able to construct any other examples where the difference is significant, but maybe someone else can spot something.

EDIT

Despite further investigation, I cannot find any cases where changing the attributes of Association make a significant difference, so I enter into speculation on the reason for the change. Here are some possibilities:

1. There is a subtle bug introduced by not having the HoldAllComplete attribute that was only discovered after the release of 10.3.1.
2. There is some performance impact of not having the attribute e.g. additional checks that need to be made for some unlikely case.
3. There is some planned new functionality that would require this attribute.
4. Association has always behaved as if it had HoldAllComplete (see https://mathematica.stackexchange.com/a/119607/36788). It is easier for users to understand and reason about if this is made explicit.

I tend to favour this final explanation.