The optimized path problem and need for time limit levels

One of the most difficult things in game design for Die 2 Escape has most definitely been the algorithm needed to find the shortest possible path from die's starting point to finish tile.
First, a die seems to be a very simple object with only 6 faces and 4 directions it can roll. However, the die can also be in 4 different positions for each face. For example if the top face is number 1, the front-facing face may be 2, 3, 5 or 4. Thus rolling the die forward might end up with any of those as die's value.
With exception of the very first level, there is a need for many moves to make the puzzle interesting. Also designing a level that cannot be solved is a very bad practice.
Each level without any moving elements can be solved beforehand using a breadth-first search algorithm. Each step in the search algorithm must include all the possible movements. If there's no blocking walls and bouncing back from them, each step would add 4 steps after each previous step. From starting position 4 steps and for each of those 4 steps ie. 16 steps. For each of those 4 steps ie. 64 steps and so on. For 9 steps the there are already over 1 million possible paths. Since there are blocking elements and elements that may cause other effects the problem gets more difficult. For example if the die bounces back from a blocking wall then the optimum move might be the backward direction.
I tried introducing randomized precalculated paths for tiles in the board and storing all the paths as simulation run.  I limited the simulation runs for maximum path search depth to 20. It did not seem to make the algorithm any faster since more memory needs to be used for the calculation. If someone has a better algorithm for this I would like to hear from you.
I have decided not to optimize path for levels with moving elements like conveyor belts where the user has the possibility to roll away during belt movement. Another possibility would have been to force the die to travel all the way on top of the conveyor belt and then the movement step were deterministic. 
This is the reason there are levels without optimum path and either some number of moves is considered as optimum or the level achievement is measured against a time limit.