The specification is 1% for x64 block, so the cheater miner only have to check 100 addresses in average, which could be done in a few ms-s.

A good solution:

Every block has two outputs:
-normal reward: 1024 and goes to the miner
-bonus reward: x0 x7 or x63 based on last block hash, and goes to the founder of the last block.