Yes, devices behind NAT are not having replies processed correctly. Kamailio forgets they're behind NAT. Without topos loaded, it's able to remember that and handles the reply correctly.
I've got several IP Phones and Asterisk behind NAT that exhibit the problem. On the other side is a Metaswitch.
This was the first major difference I spotted, but I've since uncovered further unexpected behaviour with INVITES. It appears the initial INVITE is forwarded with the modified headers and then a second INVITE is forwarded that's missing the Contact header, but is otherwise identical.