The birthday paradox only applies when you're trying to find any pair of inputs with the same output, because then the probability of success scales with the number of pairs ≈ guesses^2. If you're trying to find an input with a particular output (in this case one that results in the same key as their password), then on average you'll have to try half the search space (divided by the number of correct answers in the search space, but that should be one in this case)

I'd assume the random guesses for bitcoin miners is because with a deterministic chunk of the search space you risk the possibility that someone else chose the same chunk and so already tried all the values you're trying