Looking at the codebase, the only difference appears to be that category__not_in excludes child terms from selection, whereas cat does not.
Should category__not_in be used with caution, similar to posts__not_in? Absolutely, but for different reasons. The main issue with excluding posts is that it causes problems for caching – every query with a different excluded post ID requires a separate cache entry, significantly negating the advantage of caching. Excluding terms, meanwhile, requires more JOINs in the query, and is therefore detrimental to performance.