"As a simple, but numerically stronger example illustrating this, if we toss a coin 1000 times, then no matter what the result is, the specific observed sequence of heads and tails has a probability of only 2^−1000"
No... if you toss a coin a thousand times, the probability of observing the exact sequence you just observed is 1. It will ALWAYS happen (that's what probability 1 means). Yes, if you had an independent specification for the sequence (like writing it down before tossing the coin, or converting the binary representation to ASCII and discovering it spells "Kilroy was here") then the probability would indeed be 2^-1000; but that would be a different case.