I'm using Outlook 2007 with IMAP. I've configured sent messages to be put in the server-based "Sent" folder of my IMAP account. When I send emails, the email will briefly appear in the Sent messages folder and then disappear. They might appear for just a few seconds up to an hour or so. By "disappear" I mean that the messages are no longer in the list, and doing a search across all folders (I created a Search Folder to search for all messages) the message does not come up at all. I had a number of rules but I disabled them all and the problem still occurs. In addition I disabled AutoArchiving and ensured that there were no filters on the Sent folder.
I've not got enough magic internet points to add this as a comment but I had the same problem. even after checking all troubleshooting stuff mentioned here and elsewhere.
My solution was to delete the following:
Back up these files before deleting just in-case it breaks anything.