I assume these exchange servers are all in the same organization...
If you are positive the Logon account has FULL rights to both Exchange and a Mailbox, then confirm the mailbox is visible on the global list. In AD, check the user's properties and make sure the "Hide" option is not selected on the Exchange Advanced tab. Also, open outlook and confirm the mailbox shows up in the TO: list, and send and receive a test email to yourself with that mailbox.