To cut a long and frustrating story short, this is a known bug. The "solution" is to delete the mail data that Evolution has cached by opening a terminal window and typing the following:
ls (to get the name of the directory)
rm -rfv ./(name of directory)
I'm very grateful to the person who posted the fix here. However, this isn't really a fix. It doesn't stop the problem from occurring, it just removes the problem when it does. So why does it occur? My hunch is that the problem happens if you have your mail account open somewhere else. I'm still looking into Linux being my main laptop OS - I have (or had) my mail account open on another machine. Time will tell if just having my mail account on Fedora will prevent the problem from occurring.
But then there's another problem. Even when Evolution has correctly synchronized with Exchange and is happily connected, new mail does not show up in my Inbox. If I get new mail, the Inbox icon shows that I have an unread message, but the message itself does not appear in the Inbox. What's more, no amount of Send/Receiving or attempting to refresh the Inbox will help. The only way to see the new mail message is to shutdown Evolution and restart. This just about makes Evolution unusable as my default email client.
There is some hope, however. Fedora comes with Evolution 2.8, and version 2.8 of the Exchange Connector. New versions of both these pieces of software are available - although not via yum, or even via a rpm file. Looks like I might have to do a real Linux installation.