you can do much simpler than those algos, here.
Note: what language? Because in python, I think anyone of those should pass... :o

I was able to get my passed assertions up from 40ish randoms with dijkstra to 264 random assertions with A*, but I'm still timing out solving this ridiculous number of mazes.

Were you able to pass this? because the suite is still broken!

I would first create a DFA. If this is too hard, try thinking about how you created the DFA for multiples of 3. Then shorten this DFA with regex, removing one state each time you shorten it. Do this until you only have state A. This should work. If there are bugs try running through each compression of the DFA until you find where you did something wrong.

Or: you can write a solution using recursion, find that it works on regex101.com, then come back here to submit it and realise that in python this kata uses the re module, which does not support recursion -_-
Back to the drawing board...

the method is exactly the same. That's efectively a nightmare to make it by hand. So generally, "one" solves the 1 kyu verison first, then generate a regex from there... ;)

the python version has been updated, please try again.

seems rather like your code is inefficient. Tho there is another simpler algo you can use in this specific case.