Yes, if checking for a file is slow, then checking for a file is slow. If you need to know up front whether the module exists, then you can't get around using the "figure out whether the module exists" machinery up front. And if the definition of "a module exists" includes cases where the module is represented by a file whose existence you have to check for, then there's no getting around that, either.
(Trying to do "fallback" logic with lazily-loaded modules is also susceptible to race conditions, of course. What if someone defines the module before you try to use it?)
I have bad memories of using a network filesystem where my Python app's startup time was 5 or more seconds because of all the small file lookups for the import were really slow.
I fixed it by importing modules in functions, only when needed, so the time went down to less than a second. (It was even better using a zipimport, but for other reasons we didn't use that option.)
If I understand things correctly, your code would have the same several-second delay as it tries to resolve everything?