Can this be done?
Two organisations, complete separate domains and exchange servers.
Do I need a AD trust?
Can data be shared over HTTP or does it require a VPN connection?
One Org will have an Exchange 2010 server, the other 2007.
If both servers were running Exchange 2010 then you could use Federated Sharing to do this. You can share high level free/busy info, or more low level calendar info. It's relatively easy to setup and doesn't require AD trusts.
However, if both Exchange organisations are not using 2010, then you are limited to using the Availability Service for Cross Forest Topologies, which will only allow you to publish free/busy information to other parties. To share detail on a lower level than free/busy you would need to setup an AD trust.