I have one machine (64bit) that holds the following roles: Mailbox, Client Access, Hub Transport and Unified Messaging and it also is a domain controller and a second machine (32bit) where I have ISA Server 2006 installed and the EdgeTransport role.
I have done the preliminary steps before creating an edge subscription (install ADAM, check DNS Settings, ISA rules for allowing SMTP traffic and also for 50389 and 50636 ports), I create a new Edge Subscription, import it to the Hub Transport; when I run "Start-EdgeSynchronization", I get the following output:

Result : Success
Type : Recipients
Name : CN=isa,CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23
SPDLT),CN=Administrative Groups,CN=EXREM,CN=Microsoft Exchange
,CN=Services,CN=Configuration,DC=domain,DC=local
FailureDetails :
StartUTC : 6/8/2008 12:15:18 PM
EndUTC : 6/8/2008 12:15:18 PM
Added : 0
Deleted : 0
Updated : 1
Scanned : 53
TargetScanned : 53

Result : Success
Type : Configuration
Name : CN=isa,CN=Servers,CN=Exchange Administrative Group (FYDIBOHF23
SPDLT),CN=Administrative Groups,CN=EXREM,CN=Microsoft Exchange
,CN=Services,CN=Configuration,DC=domain,DC=local
FailureDetails :
StartUTC : 6/8/2008 12:15:18 PM
EndUTC : 6/8/2008 12:15:18 PM
Added : 0
Deleted : 0
Updated : 194
Scanned : 253
TargetScanned : 253

At a first glance, everything is working, I am able to send and receive emails.

After this, I try "Test-EdgeSynchronization"

Name : isa
LeaseHolder : DC
LeaseType : Option
ConnectionResult : Succeeded
FailureDetail :
LeaseExpiry : 6/8/2008 4:15:18 PM
LastSynchronized : 6/8/2008 3:15:18 PM
CredentialStatus : NotSynchronized
TransportServerStatus : Synchronized
TransportConfigStatus : Synchronized
AcceptedDomainStatus : Synchronized
SendConnectorStatus : Synchronized
MessageClassificationStatus : Synchronized
RecipientStatus : Synchronized

and I notice "CredentialStatus: NotSynchronized".

After some time, when I try "Test-EdgeSynchronization" again, I get:

Name : isa
LeaseHolder :
LeaseType : 0
ConnectionResult : Failed
FailureDetail : The supplied credential is invalid.
LeaseExpiry : 1/1/0001 12:00:00 AM
LastSynchronized : 1/1/0001 12:00:00 AM
CredentialStatus : Skipped
TransportServerStatus : Skipped
TransportConfigStatus : Skipped
AcceptedDomainStatus : Skipped
SendConnectorStatus : Skipped
MessageClassificationStatus : Skipped
RecipientStatus : Skipped

I have tried to delete this subscription and add it again for a few times in the last week (also restarting Exchange related services from both machines), but this behavior doesn't change.