I've seen relatively small companies take 6 months to fire someone, simply because they "have" to follow policy and procedures. Document it. Put them on a PIP. Follow up. Document it. More meetings. Document it. Meanwhile, coworkers who know this is happening are getting more and more annoyed picking up slack for this person. It'd be cheaper to pay people to leave.

"Management one level above you wants to fire you" and "the CEO said anyone who ignores him is getting fired" are two very different grades of problem.