But it seems that this is allowed by the Standard, because moving a size-K vector doesn't move any of its elements, and the "complexity requirements" are "stated solely in terms of the number of operations" on the contained int objects.

I disagree with a part of the above statement. Moving a vector does move its elements.

All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [ Example: The copy constructor of type vector<vector> has linear complexity, even though the complexity of copying each contained vector is itself linear. — end example ]

I interpret this as just saying we cannot blame the container for how difficult it is to move its elements. The type of an element is in the control of the user.

So the copy constructor of type vector<BlackBox> has linear time, even though a BlackBox element could take an unbounded amount of time to be created/moved/copied.

To give a silly example, what if the copy constructor, or the move constructor of BlackBox wants to solve the P versus NP problem before completing its execution. This time should not count towards the time complexity of the vector.