Kashrus certification agencies are legally-recognized (according to local law) entities whose business is the certification of the kosher status of restaurants, food-processing plants, etc. Restaurants hire these agencies (i.e. pay them money) to supervise the preparation and cooking of food and to publicly state that they have done so and that the aforementioned preparation and cooking was done in accordance with the laws of kashrus according to the agency's well-known standards.
This is a purely business relationship whose terms are no different than any other business relationship. Unless the contract between the two businesses specifies that the agency will never withdraw certification for any reason other than kashrus violations (which would be an extremely burdensome stipulation, which seems unlikely that any agency would agree to), the agency should certainly be able to terminate the business relationship within the bounds of halakha.