As to your general question, there is a method which is better than the inefficient solution you give. -- Namely, compute spheres of radii $r = 1, 2, \dots$ with respect to the word metric about the identity and about the element $m$ to be factored, until these spheres intersect nontrivially. This way you always get the shortest possible word as desired, and depending on the structure of your group, you save a significant amount of runtime and memory. Also, you only need to store spheres of $3$ distinct radii $r-1, r, r+1$ about each of $1$ and $m$ at a time, which further reduces memory requirements -- how much, depends again on the structure of your qroup.
That said, in general the runtime- and memory requirements of this method are still exponential in the word length; I think it is not likely that without dropping the requirement to obtain a word of minimal length you can do much better in general, as the problem of finding a word of minimal length is already hard for finite permutation groups (popular example: solving the Rubik's Cube with the smallest possible number of moves).