Hi Chris, I'm new to this forum and assuming it is OK for anyone to take a stab at an answer-if this is not the case, please speak up.
It is true that special relativity states nothing can travel faster than the speed of light and the measured speed of light must be the same in all inertial reference frames, for example, a space ship moving at substantially constant velocity. In your example, the beams of protons in the LHC are traveling toward each other at slightly less than c relative to the laboratory. However, when you say relative velocity I think you are really referring to the change in distance between the protons as they approach each other. If at some point we call that distance D and measure the time for 2 protons moving toward each other to collide then the result will about D/2c. So while you might say the distance (as measured in the laboratory) between approaching protons is changing at 2c, there is nothing actually moving faster than light. The protons are the traveling objects which in the laboratory reference frame are going slightly less than c and really only travel D/2 before collision.
The surprising observation is that from the point of view of the protons, while moving close to c in the laboratory frame, they will view the approaching protons as moving asymptotically close to but less than c according to the Lorentz transformation and described by special relativity, the equation is difficult to write here.
With the space station example, you have to travel about 17,000mph to stay in orbit above the Earth, that is the great speed and it is relative to the surface of Earth. As you point out, relative to a docking spacecraft the speed should be about zero or else we have a cosmic fender bender.
This is to the best of my understanding, hope it helps. You never know if you really understand something until you try to explain it! best wishes, don