Hi Jay,
I don't believe so, I think Mac Mail is just plain broken in 10.9.1 with certain versions of EWS. We have a bunch of Exchange servers, some on very similar--identical even--equipment/technologies. I have seen all kinds of issues, including routers with screwed up NAT rules.
I'm sure you already know this, there's so much that goes into an Exchange server, you can set it up and think you've got it configured for all situations, then stuff like this happens.
EWS is a great platform for applications to interface, if Microsoft would invested more time and effort into EWS they could have also switched Outlook on Windows to it. But they don't, and I have no idea why. I can't understand why they would want to keep RPC going when they can do it all through EWS.