If the numbers on the fax machines are managed by CUCM you can use calling search spaces on the DNs to block internal numbers. Or, on the CSS of the underlying device (an ATA presumably) the CSS of the device can simply not include the partition for internal numbers.
Similarly, if the fax machines are on a VGXXX then the trunk connecting CUCM and the VG will have an inbound calling search space. Allow partitions in that CSS to access PSTN targets (and possibly other internal fax numbers), but not the partition of internal DNs.
If the fax machines are managed by a system other than CUCM, then the connection between CUCM and the PBX managing the faxes will have a trunk and what the faxes can dial can be managed by the inbound calling search space on that trunk as well.
However, if the fax machines are randomly dialing the operator there might be a bigger issue. Do you know why the fax machines are dialing on their own?
Maren