You can have folders anywhere you want on any server(s) if the proper permissions are applied to the A2E service account.

Make sure the following Permissions are set on the 2003,  2007 or 2010 servers:

The A2E service account is part of local administrators of any Exchange Servers so it can test to see if the store is up using WMI over RPC.  This is the issue here.

Next, be sure the following Permissions are set on just the 2007 or 2010 servers.  When you run this, make sure you run this on the Exchange Server (one with Exchange PowerShell) as an Exchange Org/admin/domain admin with rights to give the Add2Exchange Service Account the appropriate rights. http://support.diditbetter.com/kb/A2E_214.aspx

Then log off of the A2E server and back on to the server as the A2E service account

Wait a bit for the exchange permissions to catch up to you and then try again to make the relationship again.

If doing a migration, this link may also be helpful: http://support.diditbetter.com/kb/A2E_191.aspx

On that link, you will see a section entitled "Change the Exchange Server Name and License Address";  reprinted here for convenience: 

1. Open regedit.exe
2. Go to key HKEY_LOCAL_MACHINE\Software\OpenDoor Software\Add2Exchange
3. Edit the value Server Name and change it to the new server name
   • Use the simple NetBIOS (cluster, if appropriate) name (i.e. Mail)
   • If the Add2Exchange Server name changed, you must specify the local machine's netbios name
4. Verify that you have gotten the server name correct and save
5. Go to the Profile 1 subkey
6. Edit the License Address key and insert a blank string - Do not remove the registry key, just open it and remove the value
7. Close regedit.
8. Open the Add2Exchange Console to have it automatically repopulate the value

Hope this helps!