Hmmm Ok, the IMEI is the equipment identification, if this has been reported as lost/stolen then its going to be barred by all the networks, and getting it removed has never been an easy thing to do
😞 On the other hand if your going on about the MSISDN (your mobile number), the barring that is on that for incoming and outgoing calls is easy to sort out.
Reading this again, looks like you should be going back to your old company and they should be buying you a new phone, if they (or any part of said company) said they had not received the phone back, then they may have had the lot barred, in which case you can seek compensation from them (which would be easier)
Tony