Back in the Windows 2000 era, a common problem was how to recover when MSMQ was allowed to build up over 1.7GB of messages. On startup, MSMQ would try and map into memory all the 4MB files in the System32\MSMQ\Storage directory. The process' virtual memory would fill up and the MSMQ service could not complete initialisation.

You receive "insufficient resources" error messages when the amount of allocated memory that is being used to store messages in Message Queuing 2.0 exceeds an amount that is between 1.6 GB and 1.8 GB

This KB article explains some of the background:

Interpreting file names in the Storage directory

The workaround is to move all the P*.MQ, L*.MQ and J*.MQ files to another directory, after which the service should start successfully (until the next time it is allowed to fill up again...). Any R*.MQ files can be discarded as they are not used for recoverable messages.

Now you still have a backup directory of MQ files containing messages that you may require to process. The messages are not lost - the storage files just need to be loaded into memory again. Obviously, you don't just copy all the files back to the Storage directory as you would be back to square one again. Instead, you copy files in batches.

It is important to understand that the MQ files exist in pairs - for example, the file P0003420.MQ requires its partner L0003420.MQ. The 4MB file contains the message data and the 8kB file is an indexing bitmap. If you lose the indexing bitmap, the message data cannot be interpreted. So when you restore the data files, don't orphan any files. For reference:

Message Queuing does not start and an Event ID 2083 error message is logged 

Another item of note is how to handle transactional messages. It is possible to send multiple messages within one transaction but MSMQ will store them in any storage file that has space. This could mean spreading the messages between multiple files (although not cutting up messages - each message is kept intact). Now you don't know - and cannot find out - which files contain all the pieces of your transaction. The result could be that, if you are restoring the files in batches, you have an incomplete transaction - which MSMQ will abort for you. If you are using single transactions (1 message - 1 transaction) then you don't have to worry.

Still on transactional messages, you need to be aware of the sequencing information that MSMQ keeps track of. As explained in the KB below, there are 5 files (QMLOG, MQInSeqs.lg1, MQInSeqs.lg2, MQTrans.lg1, MQTrans.lg2) that store the history of transactional message processing. The transactional messages in the storage files rely on the correct information in the history files. If the history data is missing or out of date then transactional messages may be duplicated. It is therefore important to not only backup the history files with the message files but also not to put any new messages into the system before processing the existing backlog.

If the problem is with the transactional message processing files then you may see the following events:

The solutions here boil down to deleting the log files and forcing MSMQ to recreate them with the LogDataCreated registry value.