Are you getting that UIDL error with IMAP or POP? (I would expect POP)
It's usually associated with the leave on server functionality or max size to avoid downloading messages capability rather than the number of messages. Pop has to fetch the entire UIDL map to match message #'s to ordinal #'s; which might be where the 'large amount of messages cause issues' descriptions you're coming across are referencing. (IMAP clients technically only need to request the 32-bit UIDs greater than the highest UID among all previously retrieved messages.)
This account that's working fine in outlook/treo/tunderbird: Are you leaving messages on the server and/or choosing a different setting in Zimbra?
If you ignore the 'slow to respond' on the IMAP can you click 'get mail' & have it work later?
Can you get some more info in /opt/zimbra/log/mailbox.log:
zmprov aal
user@domain.com zimbra.datasource debug