Exchange 2003 - Client machines do not see the exchange server

We have been having an issue with out Exchange server - basically it is buggered, with a corrupt database.  We have two backups that run on it daily - one bulk backup (entire database) and one that runs a single mailbox backup - all users mailboxes are backed up to PST's.
We found that the bulk backup has also been corrupted - something to do with a "dirty shutdown".  We are in the process of running a eseutil/p on this (so far it has taken roughly 25hours) and have got to a stage where it is imperative that we get the server up and running.
To this end, we have installed another server with Exchange 2003, and have been trying to use EXMerge to import the users data.
To do this, we are deleting the users Exchange Items through AD, and readding them with the path to the new server.  Once that is done, we are able to run EXmerge, to import the PST to the associated user account.  That all works 100%... now for the issue...
Although all the data is imported and created in the Mailbox Store, I am not able to access it from a client.

I have also just tried to create a new user, with the mail store being the new server - and am hitting the same issue, that they cannot see the server - even though they are created with their mailbox pointing to the new server store from the start.

Is there something that I have not done in the setup on the Exchange server, or is it on the client side?
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Think about the path those users use to get to the new Exchange server. Are they connecting through a firewall? Do you need to open ports on the firewall so they can reach the server? From the client computers, you can surely do a successful nslookup to the name of the old Exchange server but can you do the same for the new Exchange server? If you can't find the server name in nslookup on the client machines, Outlook can't do it either and you may need to add an A record for the server to whatever DNS server the client machines use.

These seem to be the most likely issues but it could be something else - a good place to start though.
idsafsAuthor Commented:
There are no firewalls or anything running the the new server.  We have put an A record in the AD DNS pointing to the new server - so we are able to do the nslookup, which resolves perfectly.
Is there nothing "special" that needs to be done on the Exchange server itself for integration into AD?

I can ping the new server, and access the drives from the client PC - so there is definitely a connection and it can see the server.

idsafsAuthor Commented:
The solution was the Recipient Policies, and Recipient Update Service.

Basically, I had to make sure that all users were set to get updated automatically when the Recipient Policy was updated (Email Addresses tab in User Properties in AD).
I then went into Exchange and changed the Exchange server recorded in the Recipient Update Service for both the domain and enterprise.
Once I had done this, I reapplied the Recipient Policy - which made sure that all the default email addresses showed in all users profiles - and then I rebuilt and "updated now" for the REcipient Update Services.
Re-applying, rebuilding and updating is done by rightclicking on the specific item, and selecting it from the menu.
And now I am sorted!

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.