Step 1: Communication
With any option you choose, I think, the process needs to start with a frank discussion with the moderator in question. I assume that the staff wants outspoken moderators, but doesn't want open rebellion. In this case, the discussion should solicit the moderator's feedback on what isn't working. However, the direction of the site (presumably with some input from the community) has been decided by the staff and announced. The expectation is that the moderator can follow that direction.
The moderator probably has legitimate concerns, from their point of view. Attempt to determine what those are from your discussion. The idea here is to suss out items that the staff may have missed or not anticipated. You may also discover a point of view that was completely ignored in your decisions. Reiterate the points back to the moderator in your own words to ensure that you understand what they are saying. Then, explain to them the next steps in the process (you talk to colleagues, etc. etc.). Set a reasonable date when you can get back to them with results. I'd also reiterate that you expect them to follow the announced policy in the mean time.
At some point, the staff needs to talk about some of these concerns. Some may have been brought you and discussed to death. Others may be brand new. Importance of the issues is best determined by you (or other members of the staff). Are you flexible on how policies are implemented? Are there issues that you won't (or can't) budge on? Discuss this and come up with a response. Remember that a valid response is "the policy is not changing".
Finally, follow up with the moderator team (so that everyone is on the same page). Summarize the issues, like you did at the end of your talk with the moderator individually. Once again, this shows that you understand the issues being discussed. Then explain what the outcome is. It also helps people understand your point of view if you can explain the "why", especially when they are getting a response they didn't want. "This policy isn't changing because of X and Y." It's a good idea to post these clarifications in public too, so that the entire community has a clearer idea of what is going on.
At then end of this process, if you didn't changing anything to make the rebellious moderator happy, I'd anticipate a small amount of backlash. If you have a private area for moderators, I'd allow this. It's a good time and place to further explain the why. If you don't have such an area and the backlash not stirring up the mob and handing out pitch forks, this is also a good place to explain the why. If the mob has been rallied, then it is time to do damage control...
Step 2: Use of the stick
If the moderator is performing actions to damage the community (removal of users is mentioned in the comments), then their permissions need to be revoked immediately. They have violated the trust of the staff and are no longer welcome to perform their position as moderator. Their role is to help the community flourish, and their actions have hampered that.
If the moderator continues to rally their mob of users after the discussions above have occurred, I believe they also need to have their permissions removed. It is at this point that they have gone beyond outspoken and concerned about the community to openly hostile to others (the staff). They should not be tolerating that behaviour of users toward one another. The same expectation holds for them.
Revocation of moderator permissions will generator some amount of drama. I've found that the best course of action is to present the community with a brief summary of what happened and why specific actions where taken. In the case of the moderator abusing power, it's nice and simple: "They have violated our trust by performing actions they should not have. As a result, we have removed their moderator powers. We trust our moderators to perform actions that benefit the community. This did not occur..."
If the revocation comes after the discussions and re-rallying of mob members, I'd pull portions of the discussion in the public. For me, this would include the summary of the issues brought to you, as well as the determination of what will and won't change. Make it clear that the moderator wasn't removed for having a different opinion, but for how they performed their job.
Step 3: Fall out
At the end of all of this there is the fallout. Either the moderator still has their position and has toned down their comments (win for you) or they have not and have lost their position. In either case, the staff will be asked why something did or did not occur. Try not to take these as personal attacks. People are curious and may be trying to further clarify what the policies mean. Answer the questions.
You may also need to replace a moderator after this. Start your process of selecting a new moderator. If this is done publicly, I'd mention (again) that you want moderators to share their concerns with the staff and not just be "yes men".