You don't need to guess all 128 bits of the key, just the first 65 bits, which would still probably take years of computing power.
They give half the pt so you know your key is right, you give the other half of the pt to prove it to them, probably because it's easier to type in words than a key (I wish all solutions involved typing in words). If your key is 1 bit off the entire pt is scrambled.
I think they just mistranslated "solve" or "provide" or "decrypt" into the word "guess" somewhere along the way. That's how I read it anyway, but I didn't stress it as it seems out of my reach.