I think I've figured out what's going on. Unsurprisingly, it isn't a Kamailio problem--my proposed thesis seemed as improbable to me as to all of you.
I had been going off the assumption that the absolute timestamps in the packet captures off the edge router, from which I was basing my analysis, were correct, or reasonably close to correct. It's an edge router, after all. However, the person who took them (I do not have direct access to it) just informed me that the router actually had substantial system clock drift - about 20 minutes - at the time they were taken. This invalidates the correlations I had made about the proxy log <-> capture.
As you suggested, there is most likely, in fact, a reachability or UA-related issue.