Hi Motasem,
I had this very same problem for a while. I finally had to break down and call Esri support. That was the only way to get my licenses deauthorized. They even remoted into my computer to deauthorize with no success. We had to go a "backdoor" approach that only Esri can accomplish.
There were some "changes" to the licensing at Esri lately and they are having some "server" issues apparently. You will have to call Esri Support. Please be sure to have your customer number (can be found at My Esri webpage).