I guess it would devolve to O(n^2) if you had something that really
didn't hash / a lot of collisions (for a hash table implementation),
or really unbalanced data (if you are using a tree instead of a hash
to remember what has already been seen).  Memory cost would be
something to hash it, so maybe that isn't allowed? or tunable
depending on if you optimize for speed or space.  I don't know what
implementations actually do though.

Scheme code:

(define (fons x y z)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (set-z! v) (set! z v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cbr) y)
          ((eq? m 'cdr) z)
          ((eq? m 'set-car!) set-x!)
          ((eq? m 'set-cbr!) set-y!)
          ((eq? m 'set-cdr!) set-z!)
          (else (error "Undefined operation -- FONS" m))))
  dispatch)

(define (cons x y)
  (define (set-x! v) (set! x v))
  (define (set-y! v) (set! y v))
  (define (dispatch m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          ((eq? m 'set-car!) set-x!)
          ((eq? m 'set-cdr!) set-y!)
          (else (error "Undefined operation -- CONS" m))))
  dispatch)

(define (car z) (z 'car))
(define (cdr z) (z 'cdr))

So for our software we implemented our own FAST-REMOVE-DUPLICATES
function that did use an O(n) algorithm.

In defense of the implementations, it seems like the fallback solution
has to be available to use since, unlike hash tables, REMOVE-DUPLICATES
has to accept an arbitrary test.  So a hash table solution doesn't
necessarily work, except for certain specific tests.  So it really comes
down to whether an implementation uses a special case for the (probably
relatively common) cases of EQ, EQL or EQUAL tests.

In any case, while reading the HyperSpec, I also noticed the following
interesting constraint.  I found it interesting because it is exactly
the opposite of what I would have expected:

  "The elements of sequence are compared pairwise, and if any two match,
  then the one occurring earlier in sequence is discarded, unless
  from-end is true, in which case the one later in sequence is
  discarded."

That requirement would also seem to put some constraints on the
algorithm that can be used to implement REMOVE-DUPLICATES, since the
naive hash-table implementation [where you iterate through the sequence
and only keep the elements that haven't been see before] would have the
opposite behavior.

(defun rem-dups (list &optional (hash-table (make-hash-table :size
(length list))))
  (when list
    (let ((tail (rem-dups (cdr list) hash-table)))
      (if (gethash (car list) hash-table)
          tail
        (cons (setf (gethash (car list) hash-table) (car list))
              tail)))))

(defun rem-dups (list)
  (let ((table (make-hash-table :size (length list))))
    (labels
        ((helper (rev acc)
            (if (null rev)
                acc
                (let ((elt (first rev)) (rest (rest rev)))
                  (cond
                     ((gethash elt table) (helper rest acc))
                     (t
                      (setf (gethash elt table) t
                            ;; Smash the CDR, because this will
                            ;; be a fresh
cons.
                            (cdr rev) acc)
                      (helper rest rev)))))))
       (helper (reverse list) '()))))

I looked it up in CLtL2, and after it says what you quoted, it says
the output is allowed to share a tail with the original.  So it's
optimized for getting the biggest tail possible by removing from the
front.  Saves consing and space.

I wonder if I have assumptions in my code that think remove-duplicates
provides a clean list.  Got burned by that real bad with sublis once,
so I'm aware of that type of problem, thought I wouldn't make it any
more.  I wonder if there is a list somewhere of functions allowed to
share structure?  Probably safe to assume all of them I guess.

I was thinking that it might also have something to do with the idea
that you are REMOVEing elements from the list, and you remove them in
the order encountered.  So that would also mean one might remove from
the front.  I suppose the other way would have to be called something
like KEEP-UNIQUE.  It could have the following trivial definition:

  (defun keep-unique (sequence &key :from-end &rest keys)
    (apply #'remove-duplicates sequence :from-end (not from-end) keys))