Apparently it was a problem with the VoIP client I was using.
SIPSorcery, has a setting we didn't understand at first, that makes the underlying transport exclusive to the current UserAgent. For some memory/threading optimizations.
And since our application was using multiple UserAgents, simultaneously, we would get in a weird state, that would culminate in the result posted above.
Putting in place the correct configuration for our use-case fixed that problem for good!