SIP Conversation: T38 Does Not Negotiate For A Successful Fax

WE had this fax problem that when the customer tried to dial any toll free numbers with a fax machine, the fax would not go through.  The customer would complain that the call would connect, then end with an error.  Here is what the Telco found below.  They said that we were sending an "Bye" back to them.  Hmm, from below, it does look like they are correct.
Topology:

ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:03:46:352  10.10.10.1     10.20.30.2     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:03:46:354  10.20.30.2     10.10.10.1     Status              100 Trying                                                        

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:03:48:576  10.20.30.2     10.10.10.1     Status              183 SessnProgrss                                                  

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:03:54:384  10.20.30.2     10.10.10.1     Status              200 OK                                                            

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:03:54:499  10.10.10.1     10.20.30.2     ACK                                                                                   

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:04:00:707  10.10.10.1     10.20.30.2     BYE                                                                                   

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:04:00:771  10.20.30.2     10.10.10.1     Status              200 OK     

So one of the engineers I work with found the problem.  He found that when the Telco sent the negotiations for codec, it did not negotiate correctly, causing the failure above.  However, when he moved, in our CUCM, the search order of the codec (I think he put g729 over g711), then the call would negotiate correctly with the Telco and the fax worked correctly, as seen below.

Here is what the SIP conversation looks like now:

ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:43:055  10.10.10.1     10.20.30.2     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:43:056  10.20.30.2     10.10.10.1     Status              100 Trying                                                        

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:45:200  10.20.30.2     10.10.10.1     Status              183 SessnProgrss                                                  

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:51:001  10.20.30.2     10.10.10.1     Status              200 OK                                                            

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:51:116  10.10.10.1     10.20.30.2     ACK                                                                                   

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:52:919  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:53:420  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:54:421  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:56:421  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:56:799  10.10.10.1     10.20.30.2     Status              200 OK                                                            

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:56:942  10.20.30.2     10.10.10.1     ACK                                                                                   

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:56:964  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:57:465  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:58:467  10.20.30.2     10.10.10.1     INVITE                                                                                

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:59:513  10.10.10.1     10.20.30.2     Status              200 OK                                                            

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:14:59:651  10.20.30.2     10.10.10.1     ACK                                                                                   

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:15:34:550  10.10.10.1     10.20.30.2     BYE                                                                                   

   ADV_PIP_SCRM_MICRONODE-SIPCloudLink 10/07/2013 20:15:34:614  10.20.30.2     10.10.10.1     Status              200 OK