I also had trouble with Nokia messaging. Everything worked ok except that I was unable to send emails. The messages would simply sit in the outbox.

I've had to switch to IMAP to get emails sent out and it works fine.