asterisk users - Jul 2009 - Asterisk not ACKing some 407 Proxy Auth Required requests?

I have a problem that has developed within about the past 3 months with
my backup outgoing SIP provider (I am not sure when this problem started
since it involves only my backup provider which is used rarely).

The problem is that most (not all) outgoing calls fail during the
earliest stages of call setup, specifically after the provider sends
back a "407 Proxy Auth Required" response.  The problem is that my
server is failing to ACK this response most of the time (as determined
my looking at a Wireshark capture as summarized below).  When my server
sends the second INVITE (with credentials) the provider sends back a
"491 Request Pending" which causes my server to terminate the call
with
BYE.  I've verified this behavior with Asterisk 1.4.23 through 1.4.25.1
which goes back to the time when calls placed with this provider were
working reliably.  Again, I only have this issue with one provider for
some reason (not that I am using very many) and that provider says it
has no idea why this is happening.

Shown below are two calls placed via the same provider to the same
destination within 10 seconds of each other.  The first call fails with
my server failing to send the ACK to the 407, but the second call
succeeds with my server sending the ACK to the 407.  These calls were
placed with me hitting the redial key on the phone until I got one to go
through (less than a 10% success rate).

(In case the list software munges this report, you can view it here:
http://www.omega71.com/temp/vitelity_problem_bad_good_example_edited.txt )

This trace was generated by wireshark and edited by me to remove
identifying information, but other than that it should be considered
complete and accurate.  Does anyone have any idea what might be wrong here?

FAILED CALL:

Conv.| Time    | MY_HOST | 64.2.142.215.GIGe-net.vitel.net|
6    |186.532  |         INVITE SDP ( telephone-event)          |SIP From:
sip:ME at MY_IP_ADDR To:sip:15555551212 at outbound.vitelity.net
     |         |(5060)   ------------------>  (5060)   |
6    |186.575  |         407 Proxy Authentication Required          |SIP Status
     |         |(5060)   <------------------  (5060)   |
6    |186.780  |         INVITE SDP ( telephone-event)          |SIP From:
sip:ME at MY_IP_ADDR To:sip:15555551212 at outbound.vitelity.net
     |         |(5060)   ------------------>  (5060)   |
6    |186.825  |         491 Request Pending           |SIP Status
     |         |(5060)   <------------------  (5060)   |
6    |186.825  |         ACK       |                   |SIP Request
     |         |(5060)   ------------------>  (5060)   |
6    |186.826  |         BYE       |                   |SIP Request
     |         |(5060)   ------------------>  (5060)   |
6    |186.872  |         487 Request Terminated          |SIP Status
     |         |(5060)   <------------------  (5060)   |
6    |186.873  |         200 OK    |                   |SIP Status
     |         |(5060)   <------------------  (5060)   |

SUCCESSFUL CALL:

---------------------------------------------------------
7    |193.318  |         INVITE SDP ( telephone-event)          |SIP From:
sip:ME at MY_IP_ADDR To:sip:15555551212 at outbound.vitelity.net
     |         |(5060)   ------------------>  (5060)   |
7    |193.361  |         407 Proxy Authentication Required          |SIP Status
     |         |(5060)   <------------------  (5060)   |
7    |193.361  |         ACK       |                   |SIP Request
     |         |(5060)   ------------------>  (5060)   |
7    |193.361  |         INVITE SDP ( telephone-event)          |SIP From:
sip:ME at MY_IP_ADDR To:sip:15555551212 at outbound.vitelity.net
     |         |(5060)   ------------------>  (5060)   |
7    |193.414  |         100 Trying|                   |SIP Status
     |         |(5060)   <------------------  (5060)   |
7    |195.529  |         183 Session Progress SDP ( telephone-event)         
|SIP Status
     |         |(5060)   <------------------  (5060)   |
7    |195.536  |         RTP (g711U)                   |RTP Num packets:969 
Duration:19.360s SSRC:0x74A81A70
     |         |(10024)  <------------------  (12350)  |
7    |195.689  |         RTP (g711U)                   |RTP Num packets:959 
Duration:19.220s SSRC:0x5614CA99
     |         |(10024)  ------------------>  (12350)  |
7    |214.918  |         RTP (g711U)                   |RTP Num packets:626 
Duration:12.497s SSRC:0x77780128
     |         |(10024)  <------------------  (12350)  |
7    |214.920  |         200 OK SDP ( telephone-event)          |SIP Status
     |         |(5060)   <------------------  (5060)   |
7    |214.920  |         ACK       |                   |SIP Request
     |         |(5060)   ------------------>  (5060)   |
7    |214.929  |         RTP (g711U)                   |RTP Num packets:586 
Duration:11.780s SSRC:0x39936132
     |         |(10024)  ------------------>  (12350)  |
7    |227.385  |         BYE       |                   |SIP Request
     |         |(5060)   ------------------>  (5060)   |
7    |227.425  |         200 OK    |                   |SIP Status
     |         |(5060)   <------------------  (5060)   |