Q: How can I remove the primary Microsoft Exchange attributes from all users after deleting Exchange server from my environment, so I can install Exchange fresh?

A: To remove Exchange, it should be cleanly uninstalled. If you just delete the Exchange server then try to reinstall Exchange, you will receive errors that the database is mandatory on UserMailbox.

To remove all Exchange attributes, run the following Windows PowerShell command. After it's run, there should no longer be any Exchange attributes on user mailboxes. Only do these actions if there are NO Exchange servers left in your environment, as this process wipes away the user Exchange attributes and deletes Exchange objects from Active Directory (AD):

get-aduser -filter {msExchMailboxGuid -like "*"} | set-aduser -clear msExchMailboxGuid,msexchhomeservername,legacyexchangedn,mail,mailnickname,msexchmailboxsecuritydescriptor,msexchpoliciesincluded,msexchrecipientdisplaytype,msexchrecipienttypedetails,msexchumdtmfmap,msexchuseraccountcontrol,msexchversion

Additionally, delete the CN=FederatedEmail.... account in the Users container. You'll find this documented at "When you try to install the Exchange Server 2010 Mailbox role, the installation process fails." 

If you have a Microsoft Exchange System Object container in your domain (which is visible in Active Directory Users and Computers with the Advanced Features view enabled or via ADSIEdit), you should also delete this. There are also containers in the Configuration partition of the forest under Services, named Microsoft Exchange and Microsoft Exchange Autodiscover, which you should delete using ADSIEdit.msc.

Exchange should now install without issue.