> There needs to be sufficient deterrent to actually stop this from happening
One ship might be considered a reasonable pawn to sacrifice. I'd go further: require that any ships passing through the strait to be bonded at some eye-watering amount like 10x the price of the ship plus the repair costs of the cable. Make it so if the cable is cut, you make a profit.
If these ships are independent operators being influenced by Russia, seizing the ship will be a significant consequence because the next time Russia will have a harder time convincing a crew to sabotage a cable.
Only works if you find someone to pay. I listened to a lengthy (German) podcast about international maritime law. To sum it up: you can’t do that much, because you won’t find the responsible person/company/state.