The device license of an enrolled device is always immediately released if it has been deleted on the MobiControl server side.  The device icon will be removed from device views in the web console.  Depending on your server version and configuration, log entries related to the deleted devices may optionally be totally removed from the SQL database.

However, a device will have its license released AFTER confirmation of its unenrolled status via live connection to the server , but its device icon and log entries in the SQL database remain intact.

If you have a lost device, and if data leakage and security are of no concern upon device un-enrollment at any unknown/uncontrollable time when the device gets connected to the server, then you can delete the device from your web console to IMMEDIATELY release the device license for use with another device.  If you attempt an unenrol action, un-enrollment will only be completed if the device gets online, and you thus have to wait for unpredictable amount of time, which does not seem practical for a lost device.

Thank you Raymond!!