Cita:
Iniciado por GeriReshef 
El problema es que si existen 100,000 nombres incorrectos y otros 1,000,000 direcciones (en la tabla #datos) te resulta en 100 billones (100,000,000,000) de operaciones de Replace que en cada cual el sistema busca una subcadena dentro de una cadena.
Supongo que el sistema no utiliza mucho IO, pero sí - mucho CPU.
A partir de la versión 2012 existe la herramienta Data Quality Services que esta dedicada exactamente a estas tarreas (me parece que esto es el servicio que iislas mencionó en su respuesta). No tengo ninguna experiencia con ella.
Un último comentario: ¿porque los correctos e in correctos no estan en una tabla?
La relación entre las dos es 1:1...
Lamentablemente tengo disponible solo la versión 2005 de sql server.
Me equivoqué en el ejemplo, pueden haber 100 errores asociados a un correcto.