If you have follow my guide howto to backup exchange from Arcserve R12, but still have problems with backup the exchange server.
Try to search in global address book, in outlook if you can find the user this way, if you can’t that the problems.
In our setup we got this problem on our Hosted Exchange server, the problems was resolve with adding a user and putting it in our own global address book.
