Your logic is correct, in your segment definition you would exclude the Trait (Step 5) with a AND NOT operator.
This will work find for most S2S destinations that support unsegment. Meaning that as you have said most would qualify for the condition until they convert on step5. It depends on the destination the segment is mapped to. If the destination does not support unsegment, can you create 2 segments 1. (step1 - 4) and 2. step 5 and exclude the segment step5 on the activation side.
e.g
Segment Expressions (each of the steps are traits):
( step1 AND step2 AND step3 AND step4 ) AND NOT step5