Service Broker "TO service could not be found" Message origin: "Transport"

I am trying to send a message between to SQL Server 2005 instances on two different machines. I have checked all my routes and all my objects appear to be setup correctly. However, when running Profiler on the target machine, I receive the "This message has been dropped because the TO service could not be found. Service name: "[tcp://mydomain.com/TARGET/MyService]". Message origin: "Transport". This is my activated stored procedure that is sending the message to the target service. I am using certificate security. Any help appreciated....

CREATE PROCEDURE [usp_ProcessMessage]

SET NOCOUNT ON;

DECLARE @conversation_handle uniqueidentifier

DECLARE @message_body AS VARBINARY(MAX)

WHILE (1=1)

BEGIN

BEGIN TRANSACTION;

WAITFOR(RECEIVE TOP (1)

@conversation_handle = conversation_handle,

@message_body = message_body

FROM [tcp://mydomain.com/INITIATE/MyQueue]

), TIMEOUT 1000;

IF (@@ROWCOUNT = 0)

BEGIN

COMMIT;

BREAK;

END

END CONVERSATION @conversation_handle

IF @message_body IS NOT NULL

BEGIN

BEGIN DIALOG CONVERSATION @conversation_handle

FROM SERVICE [tcp://mydomain.com/INITIATE/MyService]

TO SERVICE '[tcp://mydomain.com/TARGET/MyService]'

ON CONTRACT [tcp://mydomain.com/INITIATE/MyMessage/v1.0]

WITH ENCRYPTION = ON, LIFETIME = 600;

SEND ON CONVERSATION @conversation_handle

MESSAGE TYPE [tcp://mydomain.com/TARGET/VisitMessage]

(@message_body);

END

COMMIT;

END

OK, well I'm not sure if this is promising or not, but now my trace shows:

This message could not be delivered because the Service Contract could not be found. Service Contract: 'tcp://mydomain.com/INITATE/MyMessage/v1.0.

I see this contract defined on both the initiator and target machines.

OK, so I seem to have solved the problem by applying the following to the Target:

GRANT CONTROL ON SERVICE :: [tcp://mydomain.com/TARGET/MyService] TO PUBLIC

ALTER DATABASE [Target] SET TRUSTWORTHY ON;

and this to the Initiator:

ALTER DATABASE [Initiator] SET TRUSTWORTHY ON;

However, I'm wondering if all this is necessary. Opening up security always makes me nervous, so what is the minimum necessary to allow communication between two instances across machine/network boundaries