Why do my Android text messages (SMS) take minutes to send? 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 &amp; 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.
The HTC Mail and Messaging apps may have memory leak issues -- if this is the case, having a large DB of messages could cause a slowdown.

I had some system slowdowns and freezes. After I started using the K9Mail/Gmail and Handcent SMS apps -- I had no more slowdowns or freezes.

Since HTC apps cannot be uninstalled or turned off (unless you root), you can only set them to never poll for messages and never alert upon receipt of message. Which it shouldn't get. But you never know.