why do you need to remove it? setup re-enrolment options as required.. they are just 'new' devices.. 

But the record for the mac exists in Jamf and it causes an issue when Re-enrolling. So we have to delete them from jamf before re-enrolling. Or do you not have to remove a device from Jamf before re re-enrolling?

we don't delete any devices out of jamf unless they are sold or broken.

This keeps the audit trail. 

as long as your re-enrolment config is correct, it will wipe all previous settings and enrol as a new device, while keeping key info..

 this does of course required your polices etc to be correctly configured.. 

What would be a correct enrollment Policy that enrolls the device and removes any previous iteration of it? 

Settings > Global > Re-enrollment > Clear policy logs on computers, if you are attempting to ensure all of your policies run again once a device is re-enrolled. This is effectively treating it as a new device in terms of policies.

Thanks so much!