Hello,
look at:
http://kamailio.org/docs/modules/stable/modules/tm.html#tm.p.cancel_b_method
Maybe one or another value for that parameter is suiting better your use case.
Thank you for the suggestion.
This looked promising, but the cancel_b_method parameter is already at the default value of one. I also tried changing the value to two and got a similar result.
This may sound crazy, but it almost seems like the problem happens only when kamailio is processing unrelated INVITES at the same time.