Still having the problems - it's seems to actually be two different issues with similar symptoms:
1. Outlook Anywhere users are prompted for credentials to the Outlook anywhere hostname (listed in the authentication realm). If they do not/cannot enter credentials, then they are disconnected from the server and do not receive mail.
2. Both Outlook Anywhere and TCP connected users are prompted for credentials to /OAB. If they don't/cannot enter credentials, they continue to receive mail.
Restarting IIS always fixes the problem. On the clients, I last night tried right-clicking the Outlook icon, select Connection Status, and then use the Reconnect button, which appears to have temporarily resolved the issue. Other interesting observations, a user with two open Outlook Anywhere sessions on different computers at the same time may experience the issue on one computer but not the other (although both computers do experience the issue intermittently - just not necessarily at the same time). For this reason, I think the issue relates to the IIS session.