Hello Troels,
How did you rename those users? The thing is that Exchange uses the Display Name property of a user for the Global Address List.
When renaming a user in Adaxes (both in Adaxes Administration Console and in Adaxes Web Interface), you will be prompted for the new Full Name of the user, as well as his/her First Name, Last Name, Display Name and User Logon Name. If you change the user's Full Name only, by default, the new Display Name will not be generated correctly.
I suggest that you also update the First Name and the Last Name properties, and the new Display Name will be generated correctly by the built-in User Property Pattern. Or, alternatively, you can just update only the Display Name and Full Name properties.