Я хочу зарегистрировать сообщение Poison о том, что моя служба wcf удаляется с помощью MSMQ 3.0 и Windows 2003.

Вы можете реализовать собственный IErrorHandler и связать это с вашей службой, используя пользовательское поведение. В вашей реализации проверьте, относится ли возникшее исключение к типу MsmqPoisonMessageException, и если да, выйдите и возьмите сообщение из очереди, используя System.Messaging,MessageQueue, и зарегистрируйте его.

Существует пример, который показывает, как делается большая часть этого: перемещает сообщение в другую очередь, но его изменение должно быть тривиальным, чтобы вместо этого оно просто где-то регистрировало сообщение.

Для этого есть прекрасный пример на MSDN. http://msdn.microsoft.com/en-us/library/ms751472.aspx

Возможно, вы могли бы добавить службу, подобную следующей, которая читает сообщения из вашей подозрительной очереди и регистрирует их.

<service name="YourPosionMessageHandler"
   <endpoint
address="net.msq://localhost/private/YourServiceQueue;poison"
binding="netMsmqBinding"
    />
</service>