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.