Pan gis,
Returning a license via deauthorize is different from Recovering lost license via MyEsri.
When you authorize a license on a system, the license stays on the system. When you deauthorize the license, it returns back to the licensing server so you an authorize it on other systems.
In a case, where you lost the machine the license was authorized on, crash, or other factors where you no longer have access to the machine to return the license, you can go to MyEsri to request to recover a lost license. You were unable to recover the lost license due to various reasons. For example, there may be a maximum number of return in place for your license. You can contact Esri Customer Service for the specific issue on your license.
When you mentioned you were able to deauthorize licenses on a machine, it means there was a license on the machine to deauthorize. That means you an authorize that license on another machine. It's possible your may have more than one license or you have a single license but approved to authorized twice. If you have a single use license, you're usually authorized to license a workstation and a laptop. Again contact Customer Service. The representative can tell you how many license you have and which machine it was licensed on.