My suggestion is the have 'deactivated' users not count against used licenses.
Other examples of this in the software industry is Salesforce. When a user is deactivated, they stay in the system so that you can keep all record history, and they don't count against used licenses.
The way that Wrike has is set, you must delete all history for a user if you want to use the licenses.