Changing the URL structure of a post always consists of two parts: writing the new URL in your links, and handling the new structure.

Handling the new structure

Handling the new structure is easy: because the post name (slug) is enough to identify a post, we can ignore the taxonomy you are using in the URL. In theory you should be able to use any taxonomy, but in practice you can’t without some extra tweaks.

If you use %category%, the redirect_canonical() function kicks in and tries to redirect all requests with a term from another taxonomy in the URL to one with the category (because using only one URL for each post will prevent spreading page rank for the same content). You see this when all your URLs seem to go to /uncategorized/[post-name]/. You can unhook the function entirely, or hook into it and prevent the redirect if it’s not needed.

The other option would be to use one of your custom taxonomies in the permalink structure. This will prevent redirect_canonical() from doing anything (until that function is improved to deal with custom taxonomies too), but because of an oversight in the WP 3.0 version of custom taxonomies, it won’t generate hierarchical rewrite rules (this will be fixed in 3.1).

What I tried instead, and what seems to work, is to create a “dummy” rewrite structure, called %anything%, which matches .+? (anything, but not greedy). In this case you should also re-enable the verbose page rules, because WordPress doesn’t notice that something is going on.

add_action('init', 'wpse9346_init');
function wpse9346_init()
{
    $GLOBALS['wp_rewrite']->add_rewrite_tag( '%anything%', '(.+?)', 'wpse9346_dummy=' );
    $GLOBALS['wp_rewrite']->use_verbose_page_rules = true;
}

The wpse9346_dummy parameter is ignored, so it should be rather safe to use this. My rewrite structure now is /%anything%/%postname%/.

Writing URLs of the new structure

This is the part where you have to do some thinking: if a post can be tagged with terms from different taxonomies, what taxonomy should we use to create a link to the post? Say we have one taxonomy for countries, and one for government offices. A post about Mubarak would be tagged with Egypt in one taxonomy and President in another. Should the post URL be /egypt/mubarak-steps-down/ or /president/mubarak-steps-down/? Both URLs will work and end up at the same post, but if you use my %anything% solution from above the permalink will have %anything% in it, which is of course invalid. So hook into post_link and modify the URL the way you need it to be.