How much can we compress RSA public keys?
Daniel J. Bernstein mentioned your way of compressing RSA public keys in his paper "A secure public-key signature system with extremely fast verification".
The naive way you outline roughly doubles the work for each extra bit. If there were a better method which did not run very slowly then it could be repurposed as a factoring algorithm.
So if it were possible to decompress arbitrary 104 to 128-bit strings into secure 2048-bit RSA public keys faster than factoring as David Schwartz suggests then that would be quite remarkable. Every time you ran the algorithm you'd effectively be finding the approximately equal sized factors of some 2048bit number of which you'd specified a lot of the bits.
Although there's no theoretical reason I can think of why this should be impossible, nor would it render RSA necessarily insecure, it does strike me as rather unlikely.

As you hint, a further (impractical) way to reduce the storage of the unspecified low bits of the modulus would be to store their residues modulo various small primes and reconstruct using the CRT. In theory this should save between 3 to 4 bits for a 2048-bit modulus. You save the space because you can rely on the residues not being zero.