The reason why your rule is firing anyways is because your criteria is wrong. OR means that any condition will allow the rule to fire, while AND means that all the conditions must be necessary to fire.
Let's walk through an example:
OR(
Owner.Id <> "00516000006OnYB" ,
Owner.Id <> "005G0000002YHAe" ,
Owner.Id <> "005G0000005Foy2" ,
Owner.Id <> "00516000006Tdoh" ,
Owner.Id <> "005G0000004qehs"
) &&
Order_Paperwork_Complete__c = TRUE
When Owner.Id is 00516000006OnYB:
OR(
FALSE, // It is equal, so Boolean FALSE
TRUE, // Is not equal, so Boolean TRUE
TRUE, // Ditto...
TRUE,
TRUE
) && TRUE
FALSE OR TRUE
evaluates to TRUE, so the rule triggers.
However, if you change the formula to AND:
AND(
FALSE, // It is equal, so Boolean FALSE
TRUE, // Is not equal, so Boolean TRUE
TRUE, // Ditto...
TRUE,
TRUE
) && TRUE
FALSE AND TRUE
is FALSE, so the entire formula eventually evaluates to FALSE, and the rule will not trigger.