We have been having this problem for a long time and we didn't manage to find a solution. What is happening is that some of our users are receiving some emails (random, with no connection between them) which are not visible in their Inbox but are visible on webmail and Blackberry. When they restart the outlook the email(s) are there on the correct position, based on the time of delivery.
We are running Oracle Java Communication Server 5 with Oracle Outlook Connector 7.3 and they said they never had a problem like this before. After some googling I saw that a lot of people are facing similar problems with Exchange as well so maybe this is has nothing to do with Oracle.
The users are working or Windows XP or Windows Server 2003 with Terminal Services and Outlook 2003 SP3.