I don't understand what you mean. Regex minimization is in PSPACE, so take any PSPACE complete problem, eg Q-Sat, do the reduction and apply the algorithm. Q-Sat can be solved by recursively enumerating all possibilities. So there is a method for minimizing regular expressions. It just takes a long time to run. If you have time you can probably think of an algorithm that works directly on the regex problem without doing the Q-Sat thing. It might even be faster.

Heck, there might be an algorithm that works really well in practice. People who do model checking and verification laugh PSPACE completeness in the face and are not even really concerned with undecidability.