There seems to be a hidden time factor in bribery that is based on years rather than turns elapsed (i.e. 2 years = 1 turn by default).

For instance I was able to buy a neutral catholic quarter stack for about 7000 30 turns (1 year/turn) in, but trying to buy a similar stack 60 years (2 years/turn) in, it cost quite a bit more.

Another rebel stack of 1 upgraded no experience spear militia cost about 10000 to bribe some 130 years in (2years/turn)