It is possible to change the License type in User Setup page, from Enterprise to Undefined, in order to free up licenses occupied by this user.