I just wrote a blog post about using A* to solve puzzles in my game: Mondrian. http://jefarmstrong.com/posts/building-mondrian2-astar/ I think you might find it interesting.
Can I ask, how can you miss the exact shortest path for puzzles in its version-1? I mean did you just used hard-coded levels or what?