Cannot activate a deactivated serial number

I am in the process of moving to a new machine. I am using a serial number provided by company and I had it activated on my old machine since a few years ago. When I tried to activate the same serial number on my new box it did not go through. Then I deactivated it on my old machine but that did not help either. Now my issue is I cannot even activate it again on my old machine where it was working just fine.