Borramos (o mejor guardamos el fichero .htaccess antiguo renombrado). En las configuraciones de Wordpress establecemos el tipo de permalinks por defecto (o "simple", que acaban en ?p=123.. ). Y guardamos esa configuración.
Wordpress genera un .htaccess que debe tener la siguiente pinta:
# BEGIN WordPress
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
# END WordPress
Volvemos al ajuste de permalinks, y establecemos la opción de pretty links que queremos, por ejemplo nuestro_dominio/%postname%/. Guardamos.
En la configuración de nuestro hosting compartido, donde tenemos instalado el Wordpress, buscamos un apartado donde nos permita sincronizar el .htaccess. En mi caso en Acens/Hostalia, fue un botón "Sync htaccess".
Ya está. Tenemos el blog funcionando con los enlaces permanentes con el formato que hemos elegido.