I can explain what is happening but don't have a resolution for you.
When a user clicks save on a new record the duplicate detection kicks in before the record is saved so the status of the record is "New". Your existing records have a status of "Active", therefore there is no match.
On the second save, the record already exists and is therefore Active and a match can occur.
Having looked at the rule definitions I can't see a way to achieve what you want.