Sometimes packages get split into 2 or more packages as they grow too large or drag in too many dependencies. This may be what happened to evolution. I checked with 

    $ sudo dnf search evolution | egrep -i exchange
    evolution-ews.x86_64 : Evolution extension for Exchange Web Services
    evolution-mapi.i686 : Evolution extension for MS Exchange 2007 servers
    evolution-mapi.x86_64 : Evolution extension for MS Exchange 2007 servers

that there were some extra packages available, and with

    $ sudo dnf install evolution

we can see that they are not installed by default. Searching the web finally found a [gnome page](https://help.gnome.org/users/evolution/stable/exchange-connectors-overview.html.en) *Connecting to Exchange Servers*:

>   Choosing the right connector.
     Depending on the version of the Microsoft Exchange server that you would like to connect to it is required to make sure that an additional package is installed that provides this functionality.

>    For Microsoft Exchange 2007, 2010 and newer it is recommended to use the package evolution-ews.

I don't know why you had to reboot instead of simply restarting gnome. The extra package consists mainly of shared libraries. Perhaps evolution kept a cache of what libraries were installed and didn't notice the new ones until a reboot.