Doesn't the cost to bribe drop if with the happiness level?

Anyway: To guarantee the disposal of diplomats, which are not that difficult to kill in the first place, place your assassins in a training program. Find either an enemy or eleutheroi army controlled by a captain and kill the captains as they replace each other. Their skills will climb to the point where you can even dispatch enemy generals and destruction of buildings in enemy cities is a real option. Keep some of these ruthless monsters around and the diplomat problem is greatly reduced, and don't just keep them on your own territory. Go touring!