Post with no tag permalink problem

I don’t think there is an easy way to solve this, because /some-category/some-tag/ will be used as an overview page for all posts in category some-category and with tag some-tag. If an URL like /cocktails/bloody-mary/ comes in for a post with the name bloody-mary, category cocktails and no tags, WordPress can’t split it up correctly because at that time it does not know that bloody-mary is not a tag, and should thus be a post name.

The best solution is to use a fixed string when there is no tag (untagged, like uncategorized is what I used in my answer to your related question).