I believe in this case Outlook is correct and the UIDs are out of order. If you try IMP you will find a similar problem: it tells you how many messages there should be, but it only lists those messages up to the first message that is out-of-sequence. It doesn't give any error, but it doesn't display all the messages either.
I am not too sure what the mechanism is that causes this, but I got around it by moving all my mail files from the 'cur' directory of each user's mailbox into the 'new' directory. This seemed to allow the IMAP server to reissue UIDs and it all worked from there. Users mailboxes are in the user's home directory and each has a cur/new/tmp sub-directory.
A slight problem with that though: message delivery dates all got changed to the current date, but at least I got my mail back.
-- Jason