i would personally be more likely to refund the deposit if i really wanted someone gone and it didn't clearly state the non-refundable clause in my handbook or else I might be inclined to give them half back along with their termination letter.
It is a tough one. I will have to check the wording of my contract because I am not even sure what I said now. It would be a bad situation to run into. I hope it goes well for you tonight