Для чего вы устанавливаете свойство TimeToBeReceived?
Очереди сообщений хранятся на диске, поэтому перезагрузка не должна избавляться от них, если срок их действия не истек.
Также помните, что если вы отправите сообщение в несуществующую очередь, оно будет отброшено - убедитесь, что вы настроили очередь перед его использованием.
-Adam