How to sample uniformly from a stream of elements, some of which are unsuited?
The easiest way to solve this problem might be to randomly permute the input. For example, you could compute a random permutation pi on N elements, and replace the main loop with

for s from 1 to N:
   t = pi[s]
   ...


Edit: If you want to solve this in an online fashion, here is a different suggestion. Consider first the case $B=1$ and a threshold $T$ that always holds. So given a sequence of elements, we want to select a uniformly random one in an online fashion. This is done by the following algorithm:

for t from 1 to N:
  x = input()
  with probability 1/t:
    selected = x
return selected


Now let's still assume that $B=1$, but let the threshold be arbitrary:

 count = 0
 for t from 1 to N:
   x = input()
   if P(x) &gt; T:
     count = count + 1
     with probability 1/count:
       selected = x
 return selected


Now assume we have arbitrary $B \geq 1$, but all the elements cross the threshold:

for t from 1 to N:
  x = input()
  if t &lt;= B:
    selected[t] = x
  else:
    with probability B/t:
      i = random({1,...,B})
      selected[i] = x
return selected


Finally, putting everything together:

count = 0
for t from 1 to N:
  x = input()
  if P(x) &gt; T:
    count = count + 1
    if count &lt;= B:
      selected[count] = x
    else:
      with probability B/count:
        i = random({1,...,B})
        selected[i] = x
return selected


Edit 2: Here is yet another suggestion, assuming that you know both $N$ and the number of elements crossing the threshold, let's say $M$. You choose a random subset $S$ of size $M$ of $\{1,\ldots,N\}$. You select the $k$th element crossing the threshold for each $k \in S$.

If you only have an estimate for $M$, you can try a similar algorithm in which you guess $M$ and hope for the best.

Here is pseudocode for the algorithm:

S = random subset of {1,...,N} of size M
count = 0
for t from 1 to N:
  x = input()
  if P(x) &gt; T:
    count = count + 1
    if count in S:
      select x