Taxonomy et permaliens, comment arriver à cette structure?

Re-bonjour à tous :)
Comme dit dans un de mes précédents post, je suis entrain de repenser mon site et améliorer considérablement ma structure de lien pour qu'elle soit lisible facilement par un oeil humain (et donc par google).

Bon but est d'avoir des urls comme ceci :
http://www.monsite.com/belgique/ (OK : Nom de mon custom post type)
http://www.monsite.com/belgique\_province/liege/ (OK : 1. nom de ma taxonomy, 2. nom d'une province)
http://www.monsite.com/belgique/province/liege/ (PAS OK ! Pourquoi ?)

Voici mon code qui fonctionne :

/* Post Type : Belgique */
register_post_type('belgique', array(
    'label' => __('Belgique'),
    'singular_label' => __('Belgique'),
    'public' => true,
    'show_ui' => true,
    'menu_icon' => get_stylesheet_directory_uri() .'/images/be.png',
    'capability_type' => 'post',
    'hierarchical' => false,
    'rewrite' => array('slug' => 'belgique'),
    'supports' => array('title', 'custom-fields', 'comments', 'editor' ,'author', 'thumbnail')
));
/* Taxonomy : Belgique */
register_taxonomy( 'belgique_localisation', 'belgique', array( 
    'hierarchical' => true, 
    'label' => 'Provinces', 
    'query_var' => true, 
    'rewrite' => array('slug' => 'belgique_province')

));

Mais je voudrais dans le "rewtite" mettre ceci pour avoir une url plus structurée. D'après ce que je vois sur certains posts sur le net, ça a l'air possible mais ... je tombe sur une 404 à tout les coups.

'rewrite' => array('slug' => 'belgique/province')

J'utilise une structure personnalisée qui est /%category%/%postname%/ qui fonctionne très bien avec toutes mes taxos mais une fois que je chance comme ci-dessus, il y a tout qui foire.
Avez vous une piste? Est-ce que j'oublie de faire quelque chose à part bien faire "Enregistrer les modifications" 10x de suite dans la page Permalink pour bien rafraîchir la structure?

Bien à vous,
François