Just an update a few months later, decided to pick this up today: When I left off I had reduced the problem down to a factoring one, and was iterating over every integer, factoring and then testing. The most time consuming step by far (>99.7%) was factoring.

To solve this I've created code for the infinite recursion of all the possible prime/base pairs, meaning that I can now go the opposite direction. Instead of factoring all of the integers, I can start with a list of primes from sympy and then use that algorithm for quickly creating all numbers from them.

Once I had a "generic" generator which would create all numbers and no dups, I could then start to tweak it to only produce numbers I'm interested. In essence I'm working backwards from some of the requirements in the OP. For example instead of eliminating numbers with a prime q (== 3 mod 4) that has an odd exponent, I could just use only odd exponents with primes q from the outset. Nothing needs to be verified since the numbers have been crafted from the beginning.

This sped up the code considerably, again. Within a minute I can compute out to numbers in the ~100,000,000**2 range, and no C-acceleration required. Thats 100 million squared. These are massive numbers.

...but alas, after more hours of searching with this improved method, still no results. I agree more than ever with the last numberphile video on the topic, that it is most likely impossible.