I wonder if reducing the font size for faster transmission made it worse? A larger font might have been easier to read. Probably save time in the long run.
EDIT: Actually, looking at the output of the Fax to Binary Converter program, I think that's very likely. Even I'm not 100% sure whether that 8x6 glob of pixels is a 0 or a D.
Hmmm. If nothing else, what about search-and-replacing the Word doc to replace some of the most difficult characters with clearer ones, and then reversing the process on the other end? I mean, that's ridiculously complex, but not as complex as writing a custom Fax to Binary Converter app.