Thanks for the suggestions
I chose to export/import the contacts, there were quite a few steps that I had to perform though.
This is what I did, or that I remember that I did 
- Backed up my contacts using Outlook - just in case
- Export all contacts to VCF (In People app select all contacts and then “share” to email sent to myself)
- Then I removed the Exchange/ActiveSync account to make sure it was not in use.
- I deleted all contacts in my NextCloud account
- Removed the contacts.db from the phone (all contacts would not sync to NC otherwise) - steps for this below.
- Imported contacts from the previously exported VCF (In “Settings, Apps, People” you can import from VCF)
- Made sure everything was synced to NC
- Added back the Exchange/ActiveSync account, but without choosing to sync contacts. I still need the mail/calendar to be synced for that account.
To remove the contacts.db I did this:
systemctl --user stop contactsd.service
devel-su rm /home/nemo/.local/share/system/Contacts/qtcontacts-sqlite/contacts.*
devel-su rm /home/nemo/.local/share/system/privileged/Contacts/qtcontacts-sqlite/contacts.*
# Rebooted phone