Internet address containing %Notes Domain

After years of no problems, after an upgrade of server to 8.5.1 we are having an intermittent problem with the return address having the %NotesDomain @Internetdomain. I have checked the global domain and this is disabled. The Mime settings use CN, the address fields in the location and person doc have the correct internet address. Some mails are being rejected saying the from field has a % in it. Others make it, but replies fail. What changed?