It would be interesting to get some more info about the setup, authentication, search rules, transforms, ...
Also some output like the search details of the failed call and how the registraion looks like.
Also what the call flow is. In short the more info the better.
Where do you try to match your search rule, on the neigbor zone to the RMX or the local zone (which would
be the registration).
If you match the neigbor zone I would also check what format the RMX needs, like with or without the domain.
I would also try to set the neigbor zone to infrastructure and also check if / how you can use sip.