I recently bought my first Android phone, HTC Desire Z with Android 2.2 (Froyo).
I imported all my old Nokia E71 SMSs using the Athg2Sms Android app (after converting my Nokia CSV text file to unix-ending format). All 2,000 incoming messages and 200 outgoing messages were imported.
When I try to send a message my phone practically pauses with a modal dialog box saying "Please wait...". This message can appear for 30 seconds to several minutes.
Naturally waiting this long is ridiculous. If I press the Home or Back button the message sending is cancelled and the message goes into "Drafts".
My Nokia phone would accept a message and transmit it in the background.
Have other people encountered this unacceptable sending freeze and have they found a method to fix it? (Note, no answer recommending me to clear out my inbox is acceptable - a tiny inbox is not required for a Nokia phone, neither should it be for an Android phone).
Update
(I'll edit this section as more evidence comes to light).
As per @Michael Paulukonis 's recommendation below I deleted my e-mail accounts and switched to K-9 for e-mail. Since then I've noticed that some of my SMS sends are extremely quick, like 3 seconds. However some are not - some still take over a minute. I still have 2,000+ SMS messages on the phone but perhaps the time-to-send is related to thread length - if I know any more I'll update here!
Update 2
After a month of having the phone was getting ready to throw it at a brick wall with the frustration of being forced to stand like an idiot waiting for the f*@#ing phone to unfreeze when sending messages. I'd even tried backing up all my messages using "SMS Backup & Restore", deleting all messages, and restoring again. Finally gave up and switched to Handcent. Shame on HTC for developing a truly horridly buggy application.
Update 3
I've been using Handcent for a while. This program masks the problem in that it accepts a message as soon as you press "Send" - however the message still takes a long time before it is ready to be sent over the radio - so it appears that the underlying problem must be with the Operating System (is my guess). The good news is that messages are not turned into drafts but it can still take a long time before a message is actually sent.
Update 4 On Christmas Day 2010 I downloaded a system software update v1.72.405.2 onto my HTC Desire Z in the UK. Sent ~30 messages so far, maximum delay has been 6 seconds. Seems like this system update fixed this major bug! I will update over the next week or two to confirm/deny.