Henrik has a nice solution. Here is an alternative. You can make your own replacement function that will control the order of replacements so you can do what you want. map a function into your expression and replace the new function, f[] depending on the argument.
doReplacements[expr_, value_, replacement_] :=
Module[{f},
Map[f, expr, Infinity] //. f[holdReplacement[f[value]]] -> value //.
f[value] -> replacement //. f[arg_] -> arg]
Now you can do something like:
doReplacements[{holdReplacement["A"], "A", holdReplacement["A"],
holdReplacement["B"], "B", holdReplacement["C"], "C"}, "A", "junk"]
to get
(* {"A", "junk", "A", holdReplacement["B"], "B",
holdReplacement["C"], "C"} *)
You can expand this concept to handle the association instead of a single replacement. I am not sure if there is any improvement using this approach but it is another way to do this.
FYI: holdReplacement cannot be defined -- or you can change it to some other symbol
Regards,
Neil