I was told that the carrier can deactivate Find My Phone on a company-owned phone used by a former employee who left his iCloud credentials on the device. Is this true?
Doesn't seem like it. It's possible Apple might be of some help when dealing with company phones given that there's perhaps some corporate representative and all the appropriate records of purchase/ownership, but even that isn't necessarily a given.
The 'carrier' can't do anything but block and unblock the imei. As for Apple unlocking a phone again that's sketchy at best and no one can really answer.
I was told that the carrier can deactivate Find My Phone on a company-owned phone used by a former employee who left his iCloud credentials on the device. Is this true?
The carrier can't do anything. The employer can bypass the activation lock *if* the device is supervised using MDM before it's handed out to the employee. If the device is unsupervised, bypassing activation lock is not possible. See here for some pointers.