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).