In order to help clarify why these changes to Stealth were necessary, I feel like it's important to make sure that everybody has a clearer understanding on the way Stealth values work in general.
Any time you attempt to view a cloaked target, there are two figures which are brought into consideration:
YOU: Perception (which can be modified by StealthSight, which I'll explain separately) THEM: Stealth
For the purposes of calculating the distance at which you can see through an enemy's cloak, the formula is very simple:
Perception - Stealth = Viewable Distance
Perception, for all players and critters, begins at a base value of 5000. Meanwhile, a Standard Cloak, with 50 Aux and no +Stealth skill, has a Stealth Value of 4975. (*This value is easily viewable on the ability's tooltip.)
5000 - 4975 = 25
"Viewable Distance" in STO's system space regions very simply equates to distance units, at a 1:50 ratio. So when you divide by 50, this gives you the resulting UI measurement in kilometers.
25 / 50 = .5km
What this means is that a player using an unbuffed Cloak, vs. another player or critter with an unbuffed Perception, will be invisible until they get within a distance of 0.5km or less.
This also means that every +50 of Stealth Value you add to your Cloak/MES values results in an extra 1.0km of distance you can approach your target before being seen. And that +Perception values are a linear decrease to that distance when attempting to see Cloaked enemies.
Every +1 Starship Stealth skill point grants you +0.5 Stealth Value on a linear scale. So the Bridge Officer Trait "Basic Subterfuge" which now provides a +100 Starship Stealth skill boost, provides you with an extra +50 Stealth Value when using Cloaking abilities. Or 1km of extra distance before being detected by enemies.
StealthSight is a bit more complicated. Instead of being a linear bonus to Perception Values, it is what we call internally a "Strength Factor." The way to calculate the actual Perception gained from your Stealth Detection Rating (or SDR) is as follows:
5000 * (1 + (SDR / 10000))
So, a SDR of 300 gives you a total perception of:
5000 * (1 + (0.03)) = 5150
And, just like Stealth Values, the Perception scale is linear and applies directly to distance units at the same ratio of 1:50. So a bonus Perception of 150 in this example, allows you to perceive Cloaked enemies (150 / 50 = ) 3.0km further away than you previously could with an SDR of 0.
Given the values at play here, I hope you now understand why percentage-based bonuses were simply not working along a reasonable scale.
For example, the previous implementation of Basic Subterfuge granted a +5% to Stealth Values. When applied to a standard unskilled Cloak, this brought its Stealth Value from 4975 all the way up to 5223.75 ... a difference of almost 250 Stealth, or almost 5.0km of additional Stealth distance units. That's a pretty massive bonus, and one that was only further exacerbated by the previously-available ability to stack multiple Bridge Officers with such bonuses. By replacing those percentage-based increases with more reasonable, linear bonuses, the Stealth mechanic can be more easily balanced.
Cryptic - Systems Design
Well, that explains how my ship with no Romulan bridge officers and no skill points in stealth could bump into other ships and not be seen. I had a Reman deflector, which boosted my stealth with MES 2 well over 5000 stealth. Wild.
I might consider respecing some of klinks now to get them over 5000 stealth with the cloak.