Python - 77 chars

Abusing the python bisect module. L is the low value, H is the high value

class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

here is a test run

def test(n):
    print "testing ", n
    return n>66
L,H=10,1000
    
class B:__getitem__=lambda s,n:test(n)
import bisect as b
b.bisect(B(),0,L,H)

outputs

testing  505
testing  257
testing  133
testing  71
testing  40
testing  56
testing  64
testing  68
testing  66
testing  67

Explanation:

Here is how bisect is defined. Basically it expects a list and decides whether to bisect up or down based on the value it finds by looking at a[mid]. This calls __getitem__ on a, which instead of being a list, is a class that I have defined myself.

def bisect_right(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
  
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
"""
    
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

    bisect=bisect_right
```

Python - 70 chars

def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L

test run

def test(n):
    print "testing ", n
    return n<66
L,H=10,1000
    
def B(L,H):
 while L+1<H:M=L+H;L,H=[L,M/2,H][test(M/2):][:2]
 return L
    
print B(L,H)

outputs

testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  63
testing  67
testing  65
testing  66
65

Python, 64 chars

This one is recursive, so will overflow the stack for really large input

01234567890123456789012345678901234567890123456789012345678901234567890
|         |         |         |         |         |         |         |
 B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

test run

def test(n):
    print "testing ", n
    return n<66

L,H=10,1000


B=lambda L,H:H>L+1 and B(*[L,L/2+H/2,H][test(L/2+H/2):][:2])or H

print B(L,H)

outputs

testing  505
testing  257
testing  133
testing  71
testing  40
testing  55
testing  62
testing  66
testing  64
testing  65
66

Ruby - 92 82 62 60 characters

Iterative is way shorter, but nowhere near as cool as tail recursive.

l,h=$*.map &:to_i
test(m=(l+h)/2)?l=m+1:h=m-1 while l<=h
p l

The old tail recursive method for reference

b=proc{|l,h|h<l ?l:(m=(l+h)/2;test(m)?l=m+1:h=m-1;redo)}
puts b[*$*.map(&:to_i)]

Testing script

Uses a little magic to inject the test function and runs a file consisting of purely the above code.

low = Random.rand(100)
mid = low + Random.rand(1e25)
high = mid + Random.rand(1e50)

File.open('./bisect-test-method.rb','w') do |file|
  file << "def test(value)
             value < #{mid}
           end
          "
end

puts "Using input:"
puts "  low=#{low}"
puts "  high=#{high}"
puts "  first_bad=#{mid}"
puts "Output: #{`ruby -r ./bisect-test-method golf-bisect.rb #{low} #{high}`}"

Output:

Using input:
  low=4
  high=75343785543465286986587973836706907796015092187720
  first_bad=5013102893257647460384884
Output: 5013102893257647460384884