We are trying to connect to another organization via Lync, we both have Edge and federation set up, and can connect to other federated organisations apart from each other. We are using Lync 2010 Enterprise Voice and not Office 365 which most of the posts refer to. Does anybody have any suggestions where to look?

This message wasn't sent because ------------------ doesn't have permissions on your organization's network, or because the address is incorrect. Please contact your support team.

For some reason. Lync thinks that the federated user is a users within your domain. It doesn't identify the contact as federated contact. Usually this is due to DNS resolution on the Edge Server. Try pinging to the access edge of the partner's Lync platform and also, add the domain as a trusted domain in to External access configuration in Lync control Panel