• That is probably your problem. You should not use WITH CLEANUP in you activation procedures.

    From BOL (END CONVERSATION):

    Removes all messages and catalog view entries for one side of a conversation that cannot complete normally. The other side of the conversation is not notified of the cleanup. Microsoft SQL Server drops the conversation endpoint, all messages for the conversation in the transmission queue, and all messages for the conversation in the service queue. Administrators can use this option to remove conversations which cannot complete normally. For example, if the remote service has been permanently removed, an administrator can use WITH CLEANUP to remove conversations to that service. Do not use WITH CLEANUP in the code of a Service Broker application. If END CONVERSATION WITH CLEANUP is run before the receiving endpoint acknowledges receiving a message, the sending endpoint will send the message again. This could potentially re-run the dialog.