I modified the search function to search a random, representative subset of the search space, so that the total number of valid 12-word sets can be accurately estimated without an exhaustive search.

In 133 CPU-minutes I searched 1/10,000 of the space. My original goal of an exhaustive search would thus have taken 924 CPU-days, so I'm not going to attempt that.

The search returned got 67,672,354 unique 12-word sets that match the scrambled letters. That means the total number of unique matching 12-word sets is about 677 thousand million. Each one of these sets has 479 million possible permutations. That gives a total of 324 million million million possible word sequences. Of these, 1 in 16 will pass the 4-bit SHA-256 checksum, making a valid mnemonic. Each valid mnemonic must have its master private key derived, which involves 2048 iterations of HMAC-SHA512.

The expected number of SHA-512 operations required to find the correct private key is around 21 thousand million million million, or 2^74. That is comparable to the work currently required to mine a Bitcoin block, about 2^78 SHA-256 operations.

For comparison, given 24 unique words of a 24-word mnemonic in random order, the expected number of SHA-512 operations required to find the correct private key is 2^85, i.e. 2000 times higher.

So my conclusion remains: Finding the seed is probably doable with specialized hardware, but it is nowhere near cost-effective at a 100k sat prize even discounting the hardware cost.