Yes, a single block encrypted under 2^40 distinct keys (you can generalize this to a few popular blocks, instead of just the same block encrypted over and over)

Yes, a single block encrypted under 2^40 distinct keys (you can generalize this to a few popular blocks, instead of just the same block encrypted over and over). Each key you guess during bruteforce has a 2^40/2^128 chance of being correct. After 2^88 AES operations you're likely to recover at least one key. After 2^100 you've recovered, on average, 4096 out of the 2^40 keys.