Surely it is just common sense that searching half the space obviously has a 50% chance of finding the right key

The maths of the birthday attack suggests that by randomly generating keys (as opposed to sequentially searching the space), the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be:


Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.

I'm pretty sure that the Birthday Attack is the reason why VanityGen generates keys randomly rather than sequentially