The number of iterations seem to depend on the ratio of records
to the range of security numbers allowed.
I chose a ratio of 1 to 10 and the number
of necessary iterations dropped to 4.
Here is my modified formula for 400 records:
=IF(($A$1="")+(AND(B10,COUNTIF($B$1:$B$400,B1)=1) ),B1,
RANDBETWEEN(1000,5000))