Actually, I think I have an idea...
* Use a larger set of nodes to automatically generate the 'routes' that the AI can take, taking into account platforms and level layout.
* Use the Infinite Mario AI technique of "close nodes" for short-term decisions, like avoiding projectiles or enemies. Thankfully, the Mario AI code is open-source, so anyone can check it out and figure out how it works.
newt: One of the images here gives a rather useful idea of how A* works, well, for Mario, anyway. Basically, A* uses points, or 'nodes' to determine where an AI object should go in each tick, in order to get to a goal in the shortest possible distance. If there is an obstacle where certain nodes are, the AI will ignore them and consider other nodes instead.
Using the third image in the link I provided, the first slide shows a rather basic bunch of nodes (there are generally a lot more of them), representing certain actions Mario can take, like jump to the left, go to the right while speeding up, and so on. It will pick the best option first (in this case, going to the right fast, since the goal is the end of the level), but when this is evaluated, in the third slide, there is an enemy on that node, so the AI 'backtracks', declares that node a no-go, and then picks the next-best node - jumping over the enemy while also speeding up. The AI will then pick the next best node after that, and so on.