If Unity is working and taking messages for both internal and outside (unidentified callers) there's no need to reassociate with an Exchange box, we're talking to Exchange OK.
What you're missing in that Unity folder, however, is the locaiton object. This means no networking functionality will fly at all and you'll continue getting errors in the event log (and apps like dbWalker while scream to high heaven about it).
You should be able to recreate this easily, however, assuming you're on a recent 3.1 build. I just tested this on my 3.1(5) install and it worked fine:
Run \commserver\Configmgr.exe. Select the "Configure Default Location" radio button and hit "run". The happy armadillo will jump around and then come back with a success message (hopefully).
Now run "\commserver\configurationsetup\setup.exe -sync". The sync command line parameter will have it just syncronize what's in SQL with the directory - in this case it willc reate the OU of "Unity" and then create the locations folder and the location object under it on the fly.
After that you should be good to go. If you're on an older 3.x build this gets a little trickier - you can skip the configmgr.exe setup above and just try resynching SQL in that case... assuming the SQL tables are in good shape that should work.
