I don't have a solution, but I have similar problem (over 3410711 messages). I have figured out that hte Mail send queue is the same as the performance monitor object MSExchangeIS Mailbox with counter Send Queue Size.
Also, I used a Microsoft utility called MFCMAPI to browse information store. I found looking at the SMTP mailbox more information
Expand the root container
Look for Property name PR_CONTENT_COUNT
For me, that was the same value reported by SolarWinds Exchange Monitor and performance monitor.
When I browse the items, I have a lot of messages that are NDR, undeliverable, Delivery Status Notification (Failure), Returned mail and Undelivered Mail.
From this website http://www.msexchange.org/articles_tutorials/exchange-server-2003/management-administration/Exchange-2003-System-Mailboxes.html, I found this:
The folders MTS-IN and MTS-OUT are used by Exchange Deployment Kit (EDK) connectors to transfer messages between the MTA (Microsoft Exchange Transport Agent) and the Exchange Server information store (store.exe). They are also used for X400 connectors, Exchange site connectors, and fax connectors.
Does anyone know how to delete these messages?