I saw something like this.Maybe start by looking at your UDP packet sizes. If the packet size is exceeding the MTU, then it will be fragmented, TCP is unaffected by this.
I have seen it many times when an initial INVITE message is OK, but then the proxy responds with w WWW-Authenticate, the client sends the INVITE again with the auth info, but gets no response, this is because the extra data in the auth pushed the packet over the MTU and the proxy could not parse it correctly.
Thank you for your help @Adrian FretwellYes, so the lower capture confirms it, there is fragmentation going on. The choices are 1. Switch to TCP (bigger system overhead) or 2. Reduce your UDP packet size.
One of the easiest way of reducing the UDP packet size is to limit the number of codecs you offer, thus reducing the size of the SDP body. Some of the wide band codecs like AMR put a lot of data into the SDP body.