Ich würde mal den leeren Schuh einklicken und gegen eine Lichtquelle von vorn/hinten prüfen, ob die Stege der Sohle Kontakt zum Pedal haben. Sollte der Schuh 'schweben', wird ein neues Pedal nicht viel bringen. M.E. verschleißt das Pedal nach Sohle und Cleat als Letztes.