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.
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.