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