Your previous edit was a bit closer. Change the post type rewrite slug to:
cosmetics/treatments/%treatment-type%
Then change all instances of %type% to %treatment-type% in the treatment_permalink function.
Everything should then work correctly after you flush rewrites.
For future reference, the Monkeyman rewrite analyzer plugin is very helpful for debugging rewrite rules. As I mentioned, you can also dump the contents of $wp_query to see what WordPress is trying to query for in each request. You can put something like this directly in a 404 template for quick debugging of requests that you think should not be a 404:
<pre>
<?php print_r( $wp_query ); ?>
</pre>
You’ll see a list of all query vars with their values and the resultant SQL query WordPress is sending to the database.