Algo como esto podría funcionar más rápido porque no usa la declaración IN que podría estar repitiéndose una y otra vez sobre una tabla en memoria. Haz una copia de seguridad y prueba
DELETE
FROM `table` main
WHERE STR_To_DATE( main.Timestamp , '%a %b %d %H:%i:%s CST %Y' )<
(SELECT MAX( STR_To_DATE( sub.Timestamp , '%a %b %d %H:%i:%s CST %Y' )
FROM `table` sub
WHERE sub.Retrieving_User = main.Retrieving_User )
AND main.Retrieving_User = 'userID'