Not impossible but probably not terribly easy. I would think much depends on which mail server you are using and how it stores the messages.
My mail server knowledge is skimpy at best. But there may be a mail server out there that makes it easier to access its data. I would read up a bit on your current server and investigate others.
Programs such as Spam Assassin intercept incoming messages so maybe you could write (or have written for you) a program/extension/plugin that would examine incoming mail and write to a file or db when a reply from the fax vendor is received. Maybe there is open source code out there that does something similar. You could modify it for your particular use.
All in all, sounds like something best done with something other than a PHP solution.