Not necessarily, if there's e.g. a trillion keys to try, every tried key as a 1 in 1-trillion chance to be it, so it could be found by chance after just one try.
(disclaimer, I don't know statistics, cryptography, bitcoin or chances)
Yes, but in your example the probability of finding it at the first try would be one in a trillion, which is already so small to be negligible. And 2^66 is much bigger than that.
(disclaimer, I don't know statistics, cryptography, bitcoin or chances)