ReplaceAll with Associations instead of Rules

I described this use in Is there a faster way to Map an Association? and it is documented in the Mathematica Quick Revision History for 10.0.2, though as noted in my self-answer it existed in 10.0.0 as well:

• Replace, ReplaceAll, and ReplacePart now work with Associations

Why these things are not more directly documented is a mystery, and rather frustrating, as one must guess what is and is not overloaded to work with Association and if that support is official and lasting or transient. See the answers to my similar question:

• Listable functions thread over Associations; is this documented?

FWIW, we did finally document it, probably in 10.4 or thereabouts.

Note that the bullet point in 10.0.2 references to the fact that _Association /. rules_ began to work, not that you could use an Assocation in the 2nd argument. You could always do that. That it wasn't documented as largely an oversite. But there is also an issue (which is explictly documented under Possible Issues). In an association, keys are effectively wrapped in Verbatim. This isn't typically an issue, as the normal purpose of an association is to index literal keys, but it is a difference between expr /. _Association and expr /. Normal[_Association].

Compare results

x /. <|x -> 123, x -> 456|>

456

versus

x /. {x -> 123, x -> 456}

123

It seems associations are being operated on similar to KeyValueMap[Rule]@Join@ before ReplaceAll. I would expect this behaviour considering how associations handle duplicate keys and how ReplaceAll processes a list of rules on a pattern match.