The first thing I'd do is eliminate DISTINCT in the sub-queries. It's completely unnecessary, and it costs CPU cycles at the very least. It is also probably the reason for the poor execution plan, because SQL Server can't estimate statistics and such on that, where it can on the indexes involved. I've seen that problem before.

Second, I'd look into turning the Where Not In and the Where In into joins, if at all possible. SQL Server will probably do that behind the scenes anyway, but it can help sometimes.

Do those, or at least get rid of the distincts, and check if that changes the execution plans and the run-time.

Another thing, beyond the plans, that I'd like to see before going further on performance tuning is the CPU time and I/O stats. Are you familiar with "SET STATISTICS TIME, IO ON" as a debug tool? If not, put that statement at the top of the query, usually right after "SET NOCOUNT ON", and the inverse (just change "ON" to "OFF") at the bottom. Copy-and-paste the messages that generates to this forum, and we can take a look at those too. That often gives even more insight than the execution plan into what needs to be optimized.