Il perché è presto detto. La colpa degli arrotondamenti

Se alla fine della ricerca hai Ultimo = Primo + 1 e Ultimo è l'elemento trovato, vedrai che
CINT((Primo + Ultimo) / 2) ti ritorna PRIMO e quindi riesegue il loop.
Visto che hai chiesto solo consigli, e che è un esercizio, mi fermo qui.