Realistically, I doubt this will ever be a problem.  The list of frozen modules is fairly small and the loop in the C code is a lightweight.  So it isn't that big of a deal relative to the other costs involved in import.  Even if the number of frozen modules grows dramatically, it's unlikely to be a problem.

So we should probably close this.  Mostly I opened this so folks with the same observations could find it.  I'll close the issue in a few days in case I missed something.