The query plan that you have does indeed do multiple full table scans. Indeed, the logic of the query requires at least two row sources to be built from RENTAL. The minus set has to be generated on a different pass. Therefore, it does not matter how you partition the table. You will get partition elimination for each access to RENTAL, and if a full partition scan is chosen for a driving access to RENTAL then that can be done in parallel using block range granules. However, the (logically) subsequent access(es) to the RENTAL table for the minus clause cannot be done in parallel.

I would (redundantly) introduce CLIENT_ID as the leading field of the primary key, and make RENTAL an index organized table with full key compression. With a large database block size, that would permit a very efficient albeit serial index range scan access path to be used for any access with predicates against both CLIENT_ID and RENTAL_ID. What do think?

Assume that a query is performing multiple unions, intersects and minuses on full-partition-scans of a partitioned table. Am I better off ensuring that all of the data required to satisfy the query is in ONE of those partitions, forcing Oracle to go to disk just once, or am I better off ensuring that each full-partition-scan is against a DIFFERENT partition, forcing Oracle to go to lots of places and opening the door to effective use of Parallel query?

Example:

create table list (list_id number, email varchar2(50));
alter table list add primary key (list_id, email);
create table rental (rental_id number, client_id number, email
varchar2(50));
alter table rental add primary key (rental_id, email);
insert into list values (1, 'mailbox@domain');
insert into list values (1, 'mailbox@domain');
insert into list values (1, 'mailbox@domain');
insert into list values (2, 'mailbox@domain');
insert into list values (2, 'mailbox@domain');
insert into list values (2, 'mailbox@domain');
commit;
insert into rental values (1, 1, 'mailbox@domain');
insert into rental values (2, 1, 'mailbox@domain');
insert into rental values (3, 1, 'mailbox@domain');
analyze table list compute statistics;
analyze table rental compute statistics;

select email from
(
    (
    select email from list
    where list_id =1
    union
    select email from list
    where list_id =2
    )
    minus
    ( select email from rental
      where rental_id = 1
      and client_id = 1
      union
      select email from rental
      where rental_id = 2
        and client_id = 1
    )
)
intersect
( select email from rental
  where rental_id = 3
        and client_id = 1
);

Query Plan
----------
SELECT STATEMENT   Cost = 39
    INTERSECTION
        SORT UNIQUE
            VIEW
                MINUS
                    SORT UNIQUE
                        UNION-ALL
                            INDEX RANGE SCAN SYS_C006124
                            INDEX RANGE SCAN SYS_C006124
                    SORT UNIQUE
                        UNION-ALL
                            TABLE ACCESS FULL RENTAL
                            TABLE ACCESS FULL RENTAL
        SORT UNIQUE
            TABLE ACCESS FULL RENTAL