Wrong Exchange Server When Starting Outlook

Hi,
We have recently re-installed our Exchange server and given it a new name.
Everything looks good and you can access the server and use it as you should or at least almost. When I start Outlook for any user that hasn?t already configurated the new Exchange server Outlook tries to connect to the old Exchange server.
I was told to have a look with ADSI in Configuration but can?t really figure out where to look. I have looked in CN=Microsoft Exchange,CN=Services,CN=Configuration but I can?t find any trace of the old server in there or I just don?t know exactly what to look for.
Any help or pointers would be appreciated.
/Patrik