I have performed all the steps in this document here:
It's still coming up with the error message of "Mail system DLL is invalid, when I try to route an already received fax job to exchange.
I have also gone and unregistered and re-registered all the .DLL files beginning with "FXS" in the C:\Windows\System32 directory. Some of which would never un-register or re-register (fxsroute.dll being one of these)
We had this problem fixed before by simply renamng the original fxsroute.dll to fxsroute.dll.old and copying the pre-SP2 fxsroute.dll into the system32 dir. This worked for a while and then died again once we moved to our new office.
Thanks for any help.