I personally think that the only way to TAS Solomon's Key efficiently, (i.e. not having to spend 20+ hours on one level due to horrible randomness, which has happened to me), you need to fully understand the game's randomness - both in terms of what affects randomness, how it affects it, and what factors are affectable by randomness. I think this feat will take some ROM hacking skills (Bisqwit has made some progress, see
this post.) I think it will also be necessary to somehow track the RNG of the game, so you know the RNG-state of the game at any frame in the movie.
The feat described above is beyond my level, but if someone were to do the above and explain it to me, I might consider (at least helping out) TASing the game.
I can't really stress the importance of cracking the game's RNG before starting a Solomon's Key TAS. Just jumping into the game, even if you have some new strategies at hand, will likely end in despair due to the game's randomness taunting you.
With all this said, I would like to see a Solomon's Key run! I think Solomon's Key would make a nice team project/competition for a group of TASers.