Troubleshooting: First thought based on it being fresh in my mind was back pressure. (http://technet.microsoft.com/en-us/library/bb201658(EXCHG.80).aspx)
I verified that the edgetransport.exe.config file in Exchange bin folder had the setting:
add key="EnableResourceMonitoring" value="false"
This shows us that back pressure is off. The symtoms certainly cry out submission issues, so I checked the services just for fun. Sure enough, the services for mail submission, mailbox assistants, replication, and transport logs were all offline. Firing these back up solved the problem as expected.
A quick note is that submission queues are easy to see in outlook sitting in the Outbox, but in OWA it is a little trickier. They pass through the Drafts folder, and that is where the back log shows up.