I'm going to make a guess that you're not using security groups to manage the permissions on these mailboxes. I'd recommend, before you do anything else, that you create a security group for each logical grouping of users who need special permission on each mailbox, place the appropriate users into those groups, and grant permission using the groups.
(Beware-- the users' security token may be cached by the Exchange Server computer and it might not see the update group membership immediately. Depending on your environment it could take up to 2 hours in a stock configuration for the server to "see" the change. More details at http://theessentialexchange.com/blogs/michael/archive/2008/01/18/Exchange-Server-Caches.aspx if you want to know more about what I mean.)
By doing this with a group you eliminate the need to modify the permissions in the future if job roles change, etc, for the people involved. You need only specify the right group memberships for new users, changed job roles, etc, and the permissions "just work".
Using the Exchange Management Shell, grant "Full Mailbox Access", "Receive-As", and "Send-As" permission with the following commands:
Add-MailboxPermission "Mailbox Na,e" -User "DOMAIN\Group NAme" -AccessRights FullAccess
Add-ADPermission "Mailbox Name" -User "DOMAIN\Group Name" -ExtendedRights Receive-As,Send-As
Obviously, substitute in the mailbox name and group name where appropriate.
(Users with Full Mailbox Access don't have "Send As" permission-- see http://technet.microsoft.com/en-us/library/dd421860.aspx for details)
William, I think you answered your own question. (Good troubleshooting!) If you can access it from another VM on the same physical system, but NOT another system located elsewhere in the network, it's likely to be a network/firewall issue.
Try connecting from another system (laptop?) on the same switch and VLAN, with no router/firewall between you and the server. Success? If not, may be a software firewall on the VM or on the VM host. Check for both.
You can use telnet to verify whether or not a port is open and listening -- simply telnet to the port. If you see "Connected to BLAH.whatever. Escape character is '^]'." then the port is open.
Best Answer
You need to set an Active Directory right. It's called "Send As" and is distinct from "Send on Behalf" rights. In the Management Console, you can right-click on the mailbox object and select "manage send as..." which is where it should be managed in Exchange 2007. You can also set it from AD USers & Computers on the mailbox object, add an Advanced permission for the target user and grant "Send As". "Full Access" no longer grants "Send As" as of Exchange 2007, and possibly as of one of the later Exchange 2003 service-packs.