DeleteDuplicatesBy is not performing as I'd hoped. Am I missing something?

Déjà vu: a new-in-v10 function should provide a better solution to an old problem, but my enthusiasm is curbed when I run timings. This time the function is DeleteDuplicatesBy and while its performance is miles ahead of PositionIndex, I am still wondering if I am missing something or if this function was not ready for prime time.

In an effort to make this a question and short-circuit the cycle I shall summarize my question as:

1. What is the relative performance of DeleteDuplicatesBy and an obvious alternative?
2. Is there a case where the performance of this function clearly outstrips other methods?
-

The behavior described here is the same from 10.0.0 up to at least 10.1.0, with the minor exception of IndexBy.

Summary

We can look at the code of DeleteDuplicatesBy and it turns out it uses GroupBy. The test cases proposed by Mr.Wizard are all handled by some part of the code of DeleteDuplicatesBy. Other parts of this code also seem to have some issues. Most of the members of the *By family of functions seem to have side effects.

How DeleteDuplicatesBy works

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*)
oldCP = $ContextPath; (*all context stuff is just to make things more readable*)$ContextPath =
Join[$ContextPath, {"MacrosEvaluationPackagePrivate", "GeneralUtilitiesSystemPackagePrivate"}] DeleteDuplicatesBy // Information$ContextPath = oldCP


Or in v10.1.0 this may be done conveniently by using

<<GeneralUtilities
PrintDefinitions@DeleteDuplicatesBy


The most relevant definition that the previous commands display is

Self : DeleteDuplicatesBy[expr_, f_] :=
Module[{r$}, r$ = Which[!
Quiet[TrueQ[! AtomQ[expr] || AssociationQ[expr] ||
Macros$FailRHS, True, MacrosHoldSequence[ 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]]]]]]]; MacrosReleaseHoldSequence[r$] /; !