IIRC, the manual says you will only have the bribe option if you have at least 2000 denarii in your treasure. Perhaps this is the reason why you don't always get the option in the diplomacy screen, or perhaps you only get the option when you have _enough_ money to bribe that particular unit. Perhaps there are several kinds of bribing, e.g. if you give them 3.5k they will disband, but if you give em 5k they will become your troops. I'm just speculating, of course. I've been broke most of the time