With each bribe an NPC accepts, it increases a cost multiplier applied to future bribes. So, after being bribed 100 times, he will charge 100 times as much as the base price. Each NPC tracks its own bribe multiplier, so there is benefit to shopping around. Each NPC is initialized with a random cost multiplier between 0 and 10. (If you catch an NPC with a very low cost multiplier, he could do an upgrade for you for free!).
The cost multiplier decays extremely slowly. If an NPC is not bribed at all in an entire month, its bribe cost multiplier will only decay by about half.
Over time, the NPC bribe prices should rise up to whatever the market will bear.