the smallest number of keys we'd need to test to have a 50% chance of finding the right one would be:
This can't be right. The birthday paradox is about finding a collision, in other words testing the same private key twice.
Which for your calculated search space is only something like: ~3,458,770 guesses... which isn't a great deal to be honest.
I can believe it takes about 3 million guesses for a 50% chance (out of 8 trillion possibilities) to guess the same key twice. But that's not going to help you, as you'll still need to search 4 trillion keys for 50% chance of finding the right one.
Using a random search only means you test the same key several times, while you may never test some of the other keys.