If there is no such thing as velocity except with respect to a reference object, how can there be speed limits in deep space?

Because deep space is not empty. There are always distant galaxies and stars you can use to set up a frame of reference. Even locally, you can measure how far away you are from your laboratory, planet or asteroid. Special relativity only says that ABSOLUTE velocities are non-existent. All physics revolves around the concept of RELATIVE velocity, that is, how rapidly the distance between you and some reference object changes in a certain time interval. Velocity does exist as a concept, but only its relative character has any physical meaning.