Hace muchas lunas cuando inicie El Abismo de Tux cometí un error de novato y durante 5 años nunca cambié la estructura de mis permalinks.
Sin embargo hoy me levante con ganas de arreglarlo y después de buscar en el mar de plugins de wordpress y hacer un par de pruebas, el que resultó más rapido y transparente fue Permalink Finder un plugin que hace exactamente eso, evitar las paginas 404 con los links viejos y redireccionar a los post adecuados. Basta con que configuremos la nueva estructura de permalinks en Ajustes -> Enlaces permanentes y posteriormente instalemos el plugin.
En mis pruebas con 35 links aleatorios de mi blog desde facebook, google, bing y otros la dirección se comporta de manera adecuada y la única perdida para el blog fue el feedback de redes sociales, un pequeño precio a pagar por tener enlaces más SEO friendly :).