I've had similar problems with sending emails out as well and I found this report on bugs.maemo.org.

https://bugs.maemo.org/show_bug.cgi?id=5503

I believe that some people are using exchange and nokia messaging with the same email address and this is causing the email to be sent to two outboxes where it sits in limbo.

If this describes your situation please vote for this bug and also there's a temporary workaround posted there.