In a pair of records and I have looked at two sets now, one to the pair has a SFDC ID labelled old ID could this be the cause of the problem.
I will look at the access of the marketo user on the SFDC side. To see if that is the key to this are your referenced articles suggest.
To merge records I had to disable the sync between SFDC and MKTO and then establish the sync again when done. Ultimately however, this was not the solution.
The MKTO helpdesk were not able to replicate the issue however it was generally agreed that a group of records had been orphaned. The records did not appear in SFDC but appeared in MKTO. We were able to identify the orphaned records and after due consideration the only resolution avaliable was to delete the orphan records in MKTO.
Now once again it is possible to merge records without disabling the sync and the error message no longer appears.
It took along time to find the issue and resolve this situation, MKTO helpdesk really worked on this issue, so if your reading this helpdesk people, thanks again.