We have come across this problem with a number of users on our network... The user has Outlook 2007 connected to an Exchange 07 sp1 server with cached mode on.
The problem is some e-mails which were successfully sent are still kept in the outbox as well as in the sent items, the user with outlook 2007 client cant see the e-mails is the outbox however if you view the mailbox via webmail or outlook 2003 you can see the e-mails. I have also noticed if you view the file size of the mailbox the server data size is different from the local data size! (server version shows a bigger mailbox as it includes the items in the outbox) its as if the two are not syncing!
I have tried the basics for example removing the outlook profile and recreating with no joy.