**Observation #1**
To find numbers where the low 9 digits are pandigital, we don't really have to consider the whole numbers, but only their lowest 9 digits. The higher digits don't affect the low ones in addition, so once can generate the 9 lowest digits of the Fibonacci numbers easily.
These are trivially checked for being pandigital, so it's simple to generate "candidates" for the answer. This way I quickly find out the s for which has pandigital low digits.

**Observation #2**
Once we have the indices of candidates, we can directly find the numbers by using the following cool formula for Fibonacci numbers:

As you can see, the runtime of such a computation is logarithmic, and with some simple caching it's a very efficient algorithm for generating the th Fibonacci number. So I could just test my candidates for upper-digit pandigital this way, and the problem was solved in about a minute of runtime.

**Observation #3**
I'm pretty sure this can be done even more efficiently, using the golden ratio: