Acelere la unión de MySQL para verificar si hay duplicados

No hago ninguna promesa, pero aquí hay una alternativa para probar:

SELECT c.contact_id, c.contact_firstName, c.contact_lastName, RIGHT(c.contact_lastName,1) AS nameNum
    FROM (SELECT contact_firstName, contact_lastName, MIN(contact_id) AS MinID
              FROM contacts
              WHERE contact_client_id = ".$ID."
              GROUP BY contact_firstName, contact_lastName
              HAVING COUNT(*) > 1) t
        INNER JOIN contacts c
            ON t.contact_firstName = c.contact_firstName
                AND t.contact_lastName = c.contact_lastName
                AND c.contact_client_id = ".$ID."
                AND t.MinID <> c.contact_id