This is a bug in the HyperSpec and Issue ADJOIN-SPECIFICATION has been written about it on the CLiki. The relevant parts are:
Problem Description:
CLHS specifies ADJOIN behavior in presence of a :KEY argument by reference to Section 17.2.1 Satisfying a Two-Argument Test. This is incorrect, since section 17.2.1 specifies that the key function is NOT called on the ITEM parameter, but ADJOIN does, as is specified in pushnew. Proposal (ADJOIN:CLARIFICATION):
Replace:
The test, test-not, and key affect how it is determined whether item is the same as an element of list. For details, see Section 17.2.1 (Satisfying a Two-Argument Test).
by:
Whether or not item is already a member of the list is determined by comparisons using :test or :test-not. The first argument to the :test or :test-not function is the result returned by the :key function (if supplied), applied to the item; the second argument is an element of the list as returned by the :key function (if supplied). If :key is supplied, it is used to extract the part to be tested from both item and the list element.
Rationale:
Clarification of the specification of ADJOIN.
Current practice:
All implementations implement ADJOIN as specified on pushnew, and not as specified on adjoin.