Whenever I create any trigger, not just for scoring, I usually have to create two triggers: one fires upon record creation, and the other upon data value change. Unfortunately, in Marketo there is no choice like there is in a SFDC workflow rule that says "upon creation or future edit."
But your case a little bit more complicated because not only do you need to create an additional trigger for data value changes - the way that you've structured your scoring, you necessarily have to imbed - somewhere - the logic of "if this, then that" of your formula.
One way you could try to deal with this is to create a score that's a weighted average of other "absolute" scores (likely using SFDC). So in this case you would have a "company size" score that's set in absolute terms - if bucket is X then score is Y instead of +Y. That will take away the requirement to deal with all of the "previous values" logic, but it instead moves the complexity into the score formula instead.
A totally different way to approach this is to say - so what? What's the harm if the formula is not exactly precise? So what if a lead gets an extra 20 or 30 points based on a data value change?
In most scoring scoring formulas these types of errors are common, and are usually ignored if not undetected.
Because your score is not meant to be a preciseI would do nothing about it until you can show that it's causing a real business problem (ex: reps are routinely served up unacceptable leads) - which I would be very surprised if it did - and then it will be worth spending the time/effort dealing with.