Actually, "mutations" and "training" are two different things.
Training: Make something stronger.
Mutations: Alter something a bit.
Genetic algorithms use "Mutations" to help vary the generations after it's done splicing up the best of the previous generations into "offspring".
Genetic Algorithms is one of a couple of methods used to "train" an AI.
Also, you're biased towards A*.
A* is a pathfinder algorithm (that is, it searches for a path to go to next). Learning Algorithms can use pathfinder algorithms to plot their way around something.
Not to mention it can be difficult to implement (especially in platformers like Spelunky).
Pure A* isn't efficient for EVERYTHING (like, it can't play RTS or it can't power Shoppy, etc).
In contrast, learning algorithms, given enough time, can actually learn to play professionally, to the point where they seem to have superhuman abilities (like here
You don't have to implement learning algorithms in Neural Networks, though.
EDIT: Do you know there's a version of the AI you're refering to that uses Neural Networks? It controls Luigi to the exit using "sensors" to see.
Said AI used a genetic algorithm called NEAT to learn.