Unable to reestablish DB mirroring in SQL Server 2008 R2

[mmonclair]

Here's my scenario: I have been trying to re-establish mirroring on my SQL Server 2008 R2 instance since a VMWare outage took it down a few months ago. Here are the servers I'm using:

Primary- prodDB.mydomain.com, on DataCenter1
Mirror- recoveryDB.mydomain.com, on DataCenter2
Witness- testDB.mydomain.com, on DataCenter2
DataCenter1 and DataCenter2 are on different physical servers, in different locations. Each server is running in a VM on their respective data centers. Each has an external firewall and each data center is using Active Directory to route internal traffic.

When I tried to set this back up after the VMWare outage, I was able to set up security, with new endpoints and accounts for mirroring. I was able to log into the other database instances in each VM on port 1433 while setting up security. Upon trying to initialize mirroring I get the following error: "prodDB.mydomain.com:5022 cannot be reached or does not exist (Microsoft SQL Server, Error: 1418)". I used the following steps to troubleshoot this:

1. Verified that port 5022 is open and can be found in each data center and VM, using telnet.
2. Removed all previous endpoints and re-established them, making sure that 5022 was indicated as the listening port.
3. Set up new user accounts on each with sysadmin privileges.
4. Moved all VMs to DataCenter1 and added them to the same network in VMWare, and updated the hosts in AD to ensure traffic is being routed to the correct servers.
5. Set up an explicit network definition and SNAT/DNAT rules in the external firewall.
6. Checked again to verify that I can connect to each VM, from the others, on port 5022 inside the firewall.
7. Made sure that the user accounts set up for mirroring had sysadmin privileges for the database being mirrored.

When I try to set up mirroring, after all that, I can still set up connections in the Security wizard, but when I try to set up mirroring, I get the same error as above. So I've verified that the primary server can see the mirror and witness servers (at least on Port 1433), and that Port 5022 is open and receiving connections. All articles I've found online about this issue point to firewall, port, permissions and endpoint issues, but after taking steps to check and correct these issues, I am still getting this error. What else can I try?