Neither player had played with their respective team for 10 or more seasons or had a decrease in salary in their second-to-last to last year...
Holy ****.
Right, that provisions limits the amount of increase that can be offered.
The point being, that a contact decrease limit based on average salary explains not only why Randolph and Nash would be able to sign the extensions they did, but also why Duncan could not sign an extension for the amount he accepted. Further, the use of average salary instead of first or last year appears all over the NBA contract, appearing in this one additional place would not be unexpected.
Of course, you could find a counter-example, which would be an extension signed for well below the average salary of the previous contract.