I'm having the exact same problem. I have a split following another split. No matter what I seem to do though, the matches go down one path, but the complement still has all of the records. For example:
Split 1: Matches 10,000 records
Split 2: Matches 1,000 records, but the complement still has 10,000 records

Settings for my account type split

I Had the same problem also.
Found out that if there is no primary key in the inbound temp table then the complement is not working correctly.
So I needed to use one of two options:
1. keep a key field in the temporary table.
2. Adding another transition to the split and specify the complement rule instead of using the complement.
for example if the split is for 'age >18' then instead of using complement, add another out transition to the split specifying 'age<18' (and remove the check box from the complement)