I ended up reasonably working around this issue. Several posts had mentioned for similar issues that adding Cookie-based persistence on their load balancer had solved the issue for them.
I had resisted this "because I shouldn't have to", all the technical articles from Microsoft say this is no longer needed, and indeed not recommended.
But I caved, and ended up adding persistence for both OWA and ECP. The result was the issue was not completely resolved, but it became barely noticeable. The only time I experience issues is if I log out of OWA on one mailbox, and then immediately log into another. Even then, it kicks you out once, but if you try to login again it works fine.
There is no ongoing issue after this. Furthermore, I noticed the remaining issue only when moving from a 2013 to 2016 mailbox.
This isn't something our end users are likely to do, and we're nearly finished moving all our mailboxes to 2016. So I'm considering this work around "good enough".
Since we're using HA Proxy, it wasn't a big deal to add some layer 7 cookie-based persistence in the config. In fact, it only took about 5 minutes all up to figure out:
# HTTPS Outlook Web App (OWA)
backend bk_EXCHANGE_https_owa
cookie LB01 insert indirect nocache # <-- Added this
balance roundrobin
mode http
...
# Added the "cookie <name>" at the end of each CAS node definition
# These names must be unique to each node.
server n1_exch16_syd_01 172.16.10.2:80 maxconn 1000 weight 10 check cookie EXCH16-SYD-01
server n1_exch16_syd_02 172.16.10.3:80 maxconn 1000 weight 10 check cookie EXCH16-SYD-02
server n1_exch13 172.16.10.1:80 maxconn 1000 weight 10 check cookie EXCH13-SYD
Best Answer
The answer above may have worked in Exchange 2010 but wreaks havoc in OWA on 2016. OWA in Exchange 2016 likes to use resources loaded from microsoft.com and sharepoint.com (as well as the data: protocol). Also as it is above, the setting won't load any external images when browsing email in OWA.
The setting below has worked well for me in Exchange 2016.