I'm having this problem right now too. It's something to do with the way Dovecot implements message IDs, and Outlook making a hash of things.
The Dovecot Wiki
states that you need to change (or add) the /etc/dovecot.conf parameter:
pop3_uidl_format = %08Xu%08Xv
Which should make it function correctly. Unfortunately, the version of Dovecot I am using (0.99.11 on CentOS 4.5) does not appear to support this configuration option. All I have is:
pop3_uidl_uw_compat = no
which is commented out, and apparently "makes transition from UW to Dovecot smoother and avoids re-downloading mails". This option isn't described at the Dovecot wiki, so I can only assume it's been deprecated.
I really don't want to go to the hassle of upgrading dovecot on this box as it's only a temporary solution. I've uncommented the line, but I've got no idea if it will fix the problem with Outlook I guess I'll find out tomorrow when the customer starts bleating about their deleted e-mails not deleting.