ptang

You could try the following plugin, if you haven’t already. Sounds like it might be able to help you…

http://wordpress.org/extend/plugins/hikari-category-permalink/

As an aside, the following (from the codex) may be of interest to you:

For performance reasons, it is not a good idea to start your permalink structure with the category, tag, author, or postname fields. The reason is that these are text fields, and using them at the beginning of your permalink structure it takes more time for WordPress to distinguish your Post URLs from Page URLs (which always use the text “page slug” as the URL), and to compensate, WordPress stores a lot of extra information in its database (so much that sites with lots of Pages have experienced difficulties). So, it is best to have at least two path segments in your post’s permalink structure such as /%year%/%postname%/ or even /posts/%postname%/.

Finally, I assume you wrote your desired permalink examples the way you did to keep them concise within your question, but just in case you didn’t, you will probably want to end your permalinks with either %post_id% or %postname%. From the same source as above (i.e. the official docs):

Make sure to end your structure with either %post_id% or %postname% (e.g. /%year%/%monthnum%/%day%/%postname%/) so that each permalink points to an individual post.

Hope this helps…