Gah, yes - Evolution used to do that all the time for me (most likely your quota's full and it couldn't write into the sent-mail folder). Much as I hated pointlessly switching to Windows, I do consider Outlook to be marginally less bad as an email client.

A program has got to some level of awfulness when people start saying "Oh well, at least Outlook isn't as bad".