Hi James,
The BYE was indeed broken after the NOTIFY had failed. After some time, it was working again. The RR route header did contain the public FQDN though.
After some more tinkering, I finally got it working by enabling the "Use Actual Ephemeral Port in Contact with TCP/TLS" option on the Grandstream. This modifies the source port in the phone's Contact header so Kamailio replies to this one instead of default 5062 (which the phone does probably not allow).
Dries