These are some example sleep-times, mostly generated by replaying the random-states posted above.

*** *** *** Example 1:
tests$ sbcl --script wait-on-semaphore.script.lisp s4
::: Running (:SEMAPHORE-NOTIFICATION :WAIT-ON-SEMAPHORE)
.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
[ 0.1s] 48 safe remaining: T5, T7, T9, T11, T13, T15, T17, T19, T21, T23, T25, T27, T29, T31, T33, T35, T37, T39, T41, T43, T45, T47, T49, T51, T53, T55, T57, T59, T61, T63, T65, T67, T69, T71, T73, T75, T77, T79, T81, T83, T85, T87, T89, T91, T93, T95, T97, T99
*** Notes:
(#<THREAD "T1" FINISHED values: 1, 0.028918386 {1003E3B043}> 0 691)
(#<THREAD "T2" ABORTED {1003E3B413}> 1 720)
(#<THREAD "T3" FINISHED values: 2, 0.06313878 {1003E3B7E3}> 1 736)
*** Inc's:
(#<THREAD "T1" FINISHED values: 1, 0.028918386 {1003E3B043}> 0 720)
(#<THREAD "T3" FINISHED values: 2, 0.06313878 {1003E3B7E3}> 1 799)
*** Kills:
(#<THREAD "T2" ABORTED {1003E3B413}> NIL 736 736)
(#<THREAD "T4" ABORTED {1003E3BBB3}> NIL 799 799)
(#<THREAD "T6" ABORTED {1003E3C353}> NIL 875 875)
(#<THREAD "T8" ABORTED {1003E3CAF3}> NIL 929 929)
[...]
Backtrace for: #<SB-THREAD:THREAD "T5" RUNNING {1003E3BF83}>


*** *** *** Example 2:
tests$ sbcl --script wait-on-semaphore.script.lisp s2
::: Running (:SEMAPHORE-NOTIFICATION :WAIT-ON-SEMAPHORE)
.E.E.E.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
[ 0.1s] 42 safe remaining: T17, T19, T21, T23, T25, T27, T29, T31, T33, T35, T37, T39, T41, T43, T45, T47, T49, T51, T53, T55, T57, T59, T61, T63, T65, T67, T69, T71, T73, T75, T77, T79, T81, T83, T85, T87, T89, T91, T93, T95, T97, T99
*** Notes:
(#<THREAD "T1" FINISHED values: 1, 0.024494136 {1003E2B043}> 0 699)
(#<THREAD "T2" FINISHED values: 2, 0.0063797 {1003E2B413}> 1 723)
(#<THREAD "T3" FINISHED values: 3, 0.09456768 {1003E2B7E3}> 2 730)
(#<THREAD "T4" FINISHED values: 4, 0.007060051 {1003E2BBB3}> 3 825)
(#<THREAD "T5" FINISHED values: 5, 0.045601904 {1003E2BF83}> 4 832)
(#<THREAD "T6" FINISHED values: 6, 0.02261814 {1003E2C353}> 5 878)
(#<THREAD "T7" FINISHED values: 7, 0.097944714 {1003E2C723}> 6 901)
(#<THREAD "T9" FINISHED values: 8, 0.049314786 {1003E2CEC3}> 7 999)
(#<THREAD "T11" FINISHED values: 9, 0.009190631 {1003E2D663}> 8 1048)
(#<THREAD "T12" ABORTED {1003E2DA33}> 9 1058)
(#<THREAD "T13" FINISHED values: 10, 0.04782511 {1003E2DE03}> 9 1066)
(#<THREAD "T14" ABORTED {1003E2E1D3}> 10 1114)
(#<THREAD "T15" FINISHED values: 11, 0.042519607 {1003E2E5A3}> 10 1126)
*** Inc's:
(#<THREAD "T1" FINISHED values: 1, 0.024494136 {1003E2B043}> 0 723)
(#<THREAD "T2" FINISHED values: 2, 0.0063797 {1003E2B413}> 1 730)
(#<THREAD "T3" FINISHED values: 3, 0.09456768 {1003E2B7E3}> 2 825)
(#<THREAD "T4" FINISHED values: 4, 0.007060051 {1003E2BBB3}> 3 832)
(#<THREAD "T5" FINISHED values: 5, 0.045601904 {1003E2BF83}> 4 878)
(#<THREAD "T6" FINISHED values: 6, 0.02261814 {1003E2C353}> 5 900)
(#<THREAD "T7" FINISHED values: 7, 0.097944714 {1003E2C723}> 6 999)
(#<THREAD "T9" FINISHED values: 8, 0.049314786 {1003E2CEC3}> 7 1048)
(#<THREAD "T11" FINISHED values: 9, 0.009190631 {1003E2D663}> 8 1058)
(#<THREAD "T13" FINISHED values: 10, 0.04782511 {1003E2DE03}> 9 1114)
(#<THREAD "T15" FINISHED values: 11, 0.042519607 {1003E2E5A3}> 10 1168)
*** Kills:
(#<THREAD "T2" FINISHED values: 2, 0.0063797 {1003E2B413}> #<INTERRUPT-THREAD-ERROR {1004168593}> 797 797)
(#<THREAD "T4" FINISHED values: 4, 0.007060051 {1003E2BBB3}> #<INTERRUPT-THREAD-ERROR {1004168AD3}> 849 849)
(#<THREAD "T6" FINISHED values: 6, 0.02261814 {1003E2C353}> #<INTERRUPT-THREAD-ERROR {1004168FE3}> 909 909)
(#<THREAD "T8" ABORTED {1003E2CAF3}> NIL 969 969)
(#<THREAD "T10" ABORTED {1003E2D293}> NIL 1010 1010)
(#<THREAD "T12" ABORTED {1003E2DA33}> NIL 1066 1066)
(#<THREAD "T14" ABORTED {1003E2E1D3}> NIL 1125 1125)
(#<THREAD "T16" ABORTED {1003E2E973}> NIL 1168 1168)
(#<THREAD "T18" ABORTED {1003E2F113}> NIL 1260 1260)
(#<THREAD "T20" ABORTED {1003E2F8B3}> NIL 1293 1293)
[...]
Backtrace for: #<SB-THREAD:THREAD "T17" RUNNING {1003E2ED43}>


Maybe someone with more in-depth knowledge of what is expected can suggest how to proceed?