I use a Treo 700p and use it with my Zimbra account and gmail account. I haven't seen it with ActiveSync, but with my gmail account, if I read a message on my computer it won't show up on the phone. The phone will only pull down messages that are unread. This is going over IMAP, so probably completely unrelated, but I have seen missing messages.. Are you sure they're setup to use ActiveSync? We have a few users with Palm devices and no one has reported that using ActiveSync.
Perhaps I should use that as an excuse to get a new phone too
