Can we presume that the machine is clean ... and that you have checked connections to the sensor?
Are you sure the correct paper is being used (and not some cheap substitute)? I guess you are already aware that the machine can use two paper sizes (namely US "Letter" size and A4 fan-fold thermal paper); adjustment is made at the paper guide.
Try a fresh pack of paper.
Are stocks of paper being stored correctly? It's not too humid in Lusaka, is it?
Try a little alcohol and a cotton swab on the sensor. If problems persist, maybe the sensor is on the way out (that is, about to fail).