First, I have seen http://support.microsoft.com/kb/822447 and gone through the steps (with the exception of the replace string, as that seems like more of a work around than an actual solution).
I couldn't find any .net installed with the exception of KB958488, which I uninstalled and reinstalled after changing the regional settings.
We have two Exchange 2007 servers running on a Windows 2003 server and Windows 2008R2 server. This issue only effects mailboxes running on the Windows 2008R2 server.
As said, I have changed the regional settings to Swedish, made sure it is copied to all accounts, reinstalled the only trace of .net I could find and still have made no progress.
Any help would be hugely appreciated.
Edit: As pointed out this is a little unclear.
Simply put, exchange is adding email addresses as follows:
Ingmar Bergström gets both email@example.com and firstname.lastname@example.org
The "oe" that is replacing "ö" is incorrect and unwanted, it should simply be o (which is the behavior on the other server).
I just realized I pasted the wrong link in the window!