Once a site has no Exchange 5.5 servers in it, that old "Highest Priority" policy based on legacyExchangeDN isn't needed anymore. As people decommission their 5.5 servers and move to pure Exchange ...
Updated Jul 01, 2019
Version 2.0
Blog Post
When you apply a policy, if the recipient address does not match the format specified on the policy, a new primary address is generated and the existing primary is demoted to secondary. This is indeed the normal behavior, assuming that the policy has been applied. If the RUS is doing this constantly, you have values stuck in gatewayProxy as I discussed in the blog.
To stop this behavior, you can clear out gatewayProxy as I described. However, this will happen again the next time you apply the policy. You should either change the primary SMTP address on the policy to match the recipients (in your case it sounds like it should be %g%1s@domain.com ... that would be given name followed by first letter of surname - see Q285683), or uncheck "Automatically update email addresses" on the users.
To stop this behavior, you can clear out gatewayProxy as I described. However, this will happen again the next time you apply the policy. You should either change the primary SMTP address on the policy to match the recipients (in your case it sounds like it should be %g%1s@domain.com ... that would be given name followed by first letter of surname - see Q285683), or uncheck "Automatically update email addresses" on the users.