It appears that this is a bug within the software. The current fix is to uninstall and the re-install the Mail, People, Calendar, and Messaging App.
Before Uninstalling be sure to sync all your settings: Win + C -> Setting -> Change PC Settings -> Sync Your Settings. Set all to be "on"
To Uninstall the App, right click (or Long press hold) on any of the apps (Mail, Calendar, People, Messaging) and then selecting uninstall:
You'll be prompted to uninstall, just select "Uninstall" again:
Finally, open the App Store, and then search for "Mail". The first option is the "Mail, People, Message, and Calendar" app combo. Install it.
You'll have to wait for a few mins (about 5 for me) for all of the contacts, settings, and such to download and sync. After that, the problem is resolved.