We found the answer to this. It appears that our CRM was setup so that whenever a new contact is created it is automatically 'followed' by the user that created the record. In this case, when the Marketo sync user created a net new contact in Dynamics it would automatically follow that record, and unfortunately there's a limit to many contacts a user can follow. Once the 'follow' limit was hit (in our case it was 5,000), it wouldn't allow any new contacts to be created by the Marketo sync user. The solution was to bulk delete the follows from the Marketo sync users record in Dynamics. Once we did that, Marketo was able to sync new contacts back to Dynamics.