Allow duplicate slugs for posts on Custom post type in different categories/taxonomy?

A simple solution would be to use a single hierarchical post type instead of a taxonomy/non-hierarchical post type combination. A hierarchical post type allows you to assign a parent post to each post.

For an example you can test immediately, the built-in post post type in WordPress is non-hierarchical, the built-in page post type is hierarchical.

You can make a custom post type hierarchical by setting the hierarchical argument to true when you register the post type. You also need to add page-attributes to the supports argument when you register your post type, so that you will have the meta box that allows you to select a parent for each post.

In this scheme, you will first create custom posts for each of your categories, facelift, liposuction, etc.. You can then create the individual child patient-1 posts and assign the appropriate parent to each.

WordPress will allow these posts to have non-unique slugs because each will have a unique parent. This works because "behind the scenes" these posts are being queried by the full parent/child path, so WP is able to differentiate the ones with non-unique slugs.