After even more testing and a few days, other users started experiencing the problem.
It seems that the problem is not only that new emails do not appear in Outlook, but in addition to this, emails that were previously visible also disappear (at random).
In webmail, however, everything is there, but emails that disappear from Outlook are marked as "read" even if they weren't.
Downgrading to the old version seems to fix the problem and the emails "reappear" in Outlook, but the ones that were mistakenly marked as "read" remain that way.
In the new 8726 release I see this:
FIXED: Issue that could cause Outlook MAPI to not automatically sync new emails.
So, have you found (and fixed...) a bug related to the issue that I have described here?