Y por que no escribes una buena regla en el .htaccess que haga bien las redirecciones teniendo en cuenta las ids y todo?
Por ejemplo:
Código Apache:
Ver originalRewriteRule ^empresa_andalucia.php/(.*)$ /empresa.php/$1 [R=301,L]
No la he probado, pero puede funcionar, verifica luego al navegar hacia algunos de los elaces no encontrados te redirige bien a la buena pagina.
Los errores de webmaster tools iran desapareciendo poco a poco