Yes, this means you'll have to pay a severance because there is no paper trail. A typical severance (enough to cover the expected length of a job search) is a small cost, considering what you're getting in the deal: non-litigation, non-disparagement, minimal drama, and the employee moved out the same day.
as a manager, the conversations go like this:
1 - please (do/don't do) X. Hopefully this takes care of things.
2 - I said (do/don't do) X. why the fuck are you (not doing / doing) X. Now I'm unhappy, but again, hopefully this is the end of things and the employee starts doing / not doing X.
3 - (and this is what parent was talking about; I now have an employee refusing to do what I said and not providing good reasons for said refusal.) Now the conversation is: do / don't do X again and you're fired.
it isn't a decision, it's laying out consequences. Now, between steps 2 and 3, when I become aware of the doing or not doing X, I'm now moving on to the point where I have to give pretty blunt orders. I'm going to make sure my boss and potentially a peer or two, depending on which teams this employee works for, are aware of the situation and are ok with what will happen; I think that's what michaelt is talking about. There's also, obviously, a query for extenuating circumstances that they are but I am not aware of.
This is for exactly the reason you say: If you openly try but fail to get rid of someone, they may take it personally and try to "fuck up your shit".
If there's someone who can stop your threat (e.g. the employee is buddies with your boss) you go to that someone, lay out the problem and what you see as the options for solving it, and ask them for their advice. This advice will either be "go ahead" or "I'll take care of it"; in the latter case you should allow some time for them to take care of it.