why do recursive binary searches sometimes cause stack overflow for some but not all non existing inputs?

You have a problem when start and end are one index apart. In the example you’ve given, when you reach start=8 and end=9, you’ll have middle_index=8, then if array[middle_index] > search, you’ll call the function with start=8 and end=7, which is invalid, and will recurse forever.

You can fix this infinite recursion by relaxing the end condition to use <= instead of ==:

if (end <= start) and array[start] != search: return False
if (end <= start) and array[start] == search: return True

Side note – this condition could be simplified as follows:

if (end <= start): return array[start] == search