El problema de esa frase es que puede haber dos fallos diferentes en la frase, que hacen que cambie el sentido.
Si el fallo es la ausencia de YA/SCHON + tiempo verbal incorrecto, la frase se entendería como tú dices:
Also er/sie war schon mehrere Male in Mallorca, aber diese letze Mal hat er/sie neue interessante Orte entdeckt.