*Summary (including edits): DeleteDuplicatesBy does not always give the right result. Other *By functions can have side effects*
<br>
<br>

It turns out `DeleteDuplicatesBy` is not a function written in C. So it's Mr.Wizard's pure-MMA skills vs that of a WRI programmer for this one ;). 

Let's see what the definition of `DeleteDuplicatesBy` is. This can be seen by evaluating the following code

    DeleteDuplicatesBy (*to autoload some stuff*)
    ClearAttributes[DeleteDuplicatesBy, ReadProtected]
    oldCP = $ContextPath; (*all context stuff is just to make things more readable*)
    $ContextPath = 
     Join[$ContextPath, {"Macros`Evaluation`PackagePrivate`", 
       "GeneralUtilities`System`PackagePrivate`"}]
    DeleteDuplicatesBy // Information
    $ContextPath = oldCP

The most relevant definition is

>  
    Self : DeleteDuplicatesBy[expr_, f_] := 
     Module[{r$}, 
      r$ = Which[! 
         Quiet[TrueQ[! AtomQ[expr] || AssociationQ[expr] || 
            Head[expr] === SparseArray]], 
        Message[DeleteDuplicatesBy::normal, 1, "HoldForm"[Self]]; 
        Macros`$FailRHS, True, 
        Macros`HoldSequence[
         Which[ListQ[expr], Values[GroupBy[expr, f, First]], 
          AssociationQ[expr], 
          Association[Values[GroupBy[Normal[expr], f@*Last, First]]], 
          Head[expr] === SparseArray, 
          DeleteDuplicates[expr, f[#1] === f[#2] &], True, 
          expr[[Values[
             GroupBy[Table[{f[expr[[i]]], i}, {i, Length[expr]}], First, 
              First]][[All, 2]]]]]]]; 
      Macros`ReleaseHoldSequence[r$] /; ! 
        MatchQ[r$, 
         Macros`$FailRHS | Macros`HoldSequence[Macros`$FailRHS]]]

If we predict where we will end up for a list, this basically says

    DeleteDuplicatesBy[expr_, f_] := Values[GroupBy[expr, f, First]]

`GroupBy` gives an `Association`. `Values` converts it into a list again. Can't be too efficient.

**Incorrect results of DeleteDuplicatesBy**

By default we end up in the last branch in the `Which`, corresponding to `True`. It turns out this case is not being handled correctly. First I claimed this might lead to side effects, but the example I showed was bad and actually worked correctly. However, it turns out we do not always get the right result. Example

    DeleteDuplicatesBy[
     Hold[{a, 2}, {b, 1}, {c, 1}], Function[Null, Last@Unevaluated[#], HoldAll]]

>  
    Hold[{a,2},{b,1},{c,1}]

This output is not correct, as we have

    Function[Null, Last@Unevaluated[#], HoldAll][{b, 1}]
    Function[Null, Last@Unevaluated[#], HoldAll][{c, 1}]

>  
    1
    1

As an aside, in the last argument of `Which`, the following snippet occurs

    Table[{f[expr[[i]]], i}, {i, Length[expr]}]

This is kind of an anti pattern. Performance in cases like this is better when using `Map`, `Range` and `Transpose`. We can also see that the snippet does not work when `f` has a hold argument, as the code relies on `expr` to evaluate.

**Side effects of other `*By` family members**

This is actually what I thought was going wrong in `DeleteDuplicatesBy`. This should not print.

    a := Print["hello"]
    SortBy[Hold[{a, 2}, {b, 2}, {c, 1}], 
     Function[Null, Last@Unevaluated[#], HoldAll]]

>  
    "hello"
    Hold[{c,1},{a,2},{b,2}]

For the new `KeySortBy` we have

    a := Print["hello"]
    KeySortBy[Association@Unevaluated@{a -> 2, 3 -> 4}, Hold]

>  
    "hello"
    <|3->4, a->2|>

The undocumented System` function `IndexBy` also does not work with held expressions. It also doesn't give a message when the first argument is bad but still applies some rules.

`CountsBy` evaluates stuff that it shouldn't.

    a = 1;
    CountsBy[
     {Hold[a, 1], {b, 1}, Hold[a, 4]}, 
     Function[Null, Last@Unevaluated@#, HoldAll]]

>     <|1->2,4->1|>

Good old `SplitBy` only has some side effects

    SplitBy[Hold[{a, 1}, {b, 1}, {c, 2}], 
     Function[Null, Last@Unevaluated@#, HoldAll]]

>  
    hello
    Hold[Hold[{a,1},{b,1}],Hold[{c,2}]]

`MaximalBy` (and I suppose `MinimalBy`) and `GroupBy` do have not have the bonus of working with `Unevaluated` without creating side effects

    MaximalBy[Unevaluated@{Hold[a, 3], {q, 2}}, 
     Function[Null, Last@Unevaluated@#, HoldAll]]
>  
    arg
    {Hold[a,3]}


But at least we can pretend they ignore `Unevaluated` rather that they give bad results. `CountDistinctBy` and of course `GatherBy` seem to works as expected.

<br>
<br>
Conclusion: `DeleteDuplicatesBy` needs a bit of work. I think some functions in the `*By` family could be a bit better, some more than others.