Okay, so Microsoft seem to have added quite a bit of confusion with the over-type functionality in Word. Having thought that we now had this sussed, we found that one user was unable to enable over-type mode in the Advanced settings as the checkbox was disabled.
After hours of Googling, testing, experimenting, etc we stumbled upon the reason by accident.
If you have Track Changes enabled on a document you cannot enable over-type mode.
Hope this saves someone else hours of frustration!