Recuperar valores corruptos por cambios de codificación

[el-eles]

Hola!

Tengo una base de datos con una tabla que tiene cerca de 9000 registros. El problema es, que durante todos los años que la tengo y trabajo con ella, ha sufrido varios cambios de codificación (debido a mi inexperiencia y a aquello de: 'prueba-error'), por lo que algunos registros se han quedado corruptos, y al mostrarlos muestran caracteres que no se corresponden con el que realmente deberían. Valga como ejemplo:

opcií³n
csdigos
Contraseí±a
CÓDIGOS
DISTRACCIÓN
...

El caso es, que he reescrito la aplicación de forma que trabaja estrictamente en UTF8, todo, incluidos los archivos del código fuente, están codificados con él.
La base de datos, la cual voy a renovar también será estrictamente en UTF8 y aunque ahora ya se encuentra en UTF8, quiero reestructurar los datos y aprovechar para arreglar el problema de codificaciones anteriores.
¿Cómo podría convertir los caracteres corruptos a sus correspondientes correctos? Probé a sustituirlos a través de PHP y expresiones regulares, pero no realiza bien los cambios.

Muchas gracias