peter,
i don't have experience with k rls module, but in my environment if initial subscribe comes from behind nat, i just call add_contact_alias and add a nat param to r-r header for in-dialog requests. notifys from rls server then contain ;alias param in request uri and the nat param in route header. based on these sip proxy is able to get thee get notifys to the uas behind nat.
-- juha