It doesn't matter that the keys are in HEX. You can convert them to WIF and then use the according base keys to generate valid address. I encountered the same problem. WIF validation may be correct however there are way too many possible keys. What is interesting is uncompressed format there is a few less bytes to deal with, which in turn could be converted back to compressed if needed. Ill leave a couple examples here.
EC 0000000000000000000000000000000000000000000000000000000000000001
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
EC 0000000000000000000000000000000000000000000000000000000000000003
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU74sHUHy8S
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreB1FQ8BZ
EC 00000000000000000000000000000000000000000000000000000022382FACD0
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9P3MahktLW5315v
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB4BW8dsj4c9a6g
EC 000000000000000000000000000000000000000000000001A838B13505B26867 - puzzle 65
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZM21gaY8WN2CdwnTG57
5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ipCnYRNeQuRFKarWVVs
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU73sVHnoWn
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFU74sHUHy8S
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9P3MahktLW5315v
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZM21gaY8WN2CdwnTG57
So we could say upcoming puzzles private key 66 will start with...
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3
Can you show an example, for example on puzzle 80, by removing the middle part of the key? And how long will this work take?
00000000000000000000000000000000000000000000ExxxxxxxxxC11B5AD180