Interesting post on the Motley Queüe blog from April about the new Active Directory Recycle Bin feature introduced in Windows 2008 R2.
Discusses what you can (or cannot) do when you have lost Active Directory objects, such as MSMQ Public Queues, either through accidental deletion or uninstallation.
Remember that MSMQ's objects in AD have unique GUIDs so manually recreating them won't always get you back to where you started.
Active Directory Recycle Bin Step-by-Step Guide
Message Queuing and Active Directory
Active Directory Documentation Team