This is one of those horrible surprises - the system has been working fine for months; someone needs to restart the machine; everything disappears! Developers notice that Transactional messages never disappear so it must be a problem with Non-Transactional messages...
The explanation is simple - the developer of the application wrote code to just create and send a message. The defaults mean you end up with Express messages which only exist in RAM and are not persisted to the disk, so cannot survive a restart. To be persisted, the Recoverable option must be selected when the message is created. Transactional messages, by design, automatically flip the Recoverable bit which is why they never disappear after a restart.
Here's a simple table of the choices available:
Express messages are also know as "fire-and-forget". It doesn't matter if they get lost as their value it low or they are easily replaced. A good example of something that may use them is a stock ticker - it doesn't matter if one message gets lost as an updated stock price on the next message wil be along soon to replace it.
Here is a C# example from “Reliable Messaging with MSMQ and .NET” for setting the Recoverable property:
Message recoverableMessage = new Message();
recoverableMessage.Body = "Sample Recoverable Message";
recoverableMessage.Recoverable = true;
MessageQueue msgQ = new MessageQueue(@".\$private\Orders");